이진 탐색 응용 1 - getItemFromTwoSortedArrays

• naive solution

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let cnt = 0, //반복횟수
    left = 0,
    right = 0;
  let target;
  while (cnt < k) { //반복문을 k-1번 반복
    if (arr1[left] < arr2[right]) { //arr1의 0번쨰와 arr2의 0번째를 비교
      target = arr1[left]; //작은 걸 target에 할당
      left++; //그 다음 요소와 arr2[right]를 비교
    } else {
      target = arr2[right];//작은 걸 target에 할당
      right++;//그 다음 요소와 arr1[left]를 비교
    }
    cnt++;//반복횟수 1씩 증가
  }
  return target; //앞에서 k번째 작은 target이 리턴
};

• O(logK) solution(진짜 천재 아녀??)
  Math.ceil : Math.ceil() 함수는 주어진 숫자보다 크거나 같은 숫자 중 가장 작은 숫자를 integer 로 반환 -> 소수점 올림!

// O(logK) solution
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let leftIdx = 0,
    rightIdx = 0;

  while (k > 0) {
    // 이진 탐색을 위해 각 배열에서 k를 절반으로 쪼개서 카운트 한다.
    let cnt = Math.ceil(k / 2);
    let leftStep = cnt,
      rightStep = cnt;

    // 엣지 케이스
    // 카운트가 남았음에도 배열의 끝에 도달하면 k를 나머지 배열쪽으로 넘긴다.
    if (leftIdx === arr1.length) {
      rightIdx = rightIdx + k;
      break;
    }

    if (rightIdx === arr2.length) {
      leftIdx = leftIdx + k;
      break;
    }

    // 엣지 케이스
    // 현재 카운트가 남아있는 후보 요소들보다 많을 경우, leftStep(현재 할당량)을 남아있는 요소들의 개수로 바꾼다.
    if (cnt > arr1.length - leftIdx) leftStep = arr1.length - leftIdx;
    if (cnt > arr2.length - rightIdx) rightStep = arr2.length - rightIdx;

    // 두 배열의 현재 검사 요소 위치를 비교해서, 그 값이 작은 배열은 비교한 위치 앞에 있는 요소들을 모두 후보군에서 제외시킨다.
    if (arr1[leftIdx + leftStep - 1] < arr2[rightIdx + rightStep - 1]) {
      leftIdx = leftIdx + leftStep;
      // 처리가 끝나면 k값을 절반으로 떨어뜨린다.
      k = k - leftStep;
    } else {
      rightIdx = rightIdx + rightStep;
      k = k - rightStep;
    }
  }

  leftMax = arr1[leftIdx - 1] || -1;
  rightMax = arr2[rightIdx - 1] || -1;

  return Math.max(leftMax, rightMax);