오름차순 정렬된 2개의 배열에서 K번째 요소를 찾아 반환하시오

입출력예시

let arr1 = [1, 4, 8, 10];
let arr2 = [2, 3, 5, 9];
let result = getItemFromTwoSortedArrays(arr1, arr2, 6);
console.log(result); // --> 8

arr1 = [1, 1, 2, 10];
arr2 = [3, 3];
result = getItemFromTwoSortedArrays(arr1, arr2, 4);
console.log(result); // --> 3

시간복잡도 때문에 통과 아얘 안되었다. (합쳐서 정렬 후 이진탐색 시도하려 했으나, 정렬 알고리즘은 아무래 해봤자 NlogN을 벗어날 수 없기 때문에 이 방법은 안된다고 한다.)

아래 코드 출처: https://www.geeksforgeeks.org/k-th-element-two-sorted-arrays/

검색어: binary search in two sorted array

const getItemFromTwoSortedArrays = function (arr1, arr2, k) {

function kth(arr1 , arr2 , m , n , k , st1 , st2){

		// In case we have reached end of array 1
		if (st1 == m) {
			return arr2[st2 + k - 1];
		}

		// In case we have reached end of array 2
		if (st2 == n) {
			return arr1[st1 + k - 1];
		}

		// k should never reach 0 or exceed sizes
		// of arrays
		if (k == 0 || k > (m - st1) + (n - st2)) {
			return -1;
		}

		// Compare first elements of arrays and return
		if (k == 1) {
			return (arr1[st1] < arr2[st2]) ? arr1[st1] : arr2[st2];
		}
		let curr = parseInt(k / 2);

		// Size of array 1 is less than k / 2
		if (curr - 1 >= m - st1) {

			// Last element of array 1 is not kth
			// We can directly return the (k - m)th
			// element in array 2
			if (arr1[m - 1] < arr2[st2 + curr - 1]) {
				return arr2[st2 + (k - (m - st1) - 1)];
			} else {
				return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);
			}
		}

		// Size of array 2 is less than k / 2
		if (curr - 1 >= n - st2) {
			if (arr2[n - 1] < arr1[st1 + curr - 1]) {
				return arr1[st1 + (k - (n - st2) - 1)];
			} else {
				return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);
			}
		} else

		// Normal comparison, move starting index
		// of one array k / 2 to the right
		if (arr1[curr + st1 - 1] < arr2[curr + st2 - 1]) {
			return kth(arr1, arr2, m, n, k - curr, st1 + curr, st2);
		} else {
			return kth(arr1, arr2, m, n, k - curr, st1, st2 + curr);
		}
	}

    let st1 = 0;
    let st2 = 0;
    return kth(arr1,arr2,arr1.length,arr2.length,k,st1,st2)

	// // Driver code
	// 	var arr1 = [ 2, 3, 6, 7, 9 ];
	// 	var arr2 = [ 1, 4, 8, 10 ];
	// 	var k = 5;
	// 	var st1 = 0, st2 = 0;
	// 	document.write(kth(arr1, arr2, 5, 4, k, st1, st2));

};

// naive solution
/*
Error: Timeout of 2000ms exceeded. 
For async tests and hooks, ensure "done()" is called; 
if returning a Promise, ensure it resolves. (/submission/index.test.js)
*/
const getItemFromTwoSortedArrays = function (arr1, arr2, k) {
  let cnt = 0, //반복 횟수를 제한하기 위한변수: K 번째 요소를 찾아야 하므로, K-1번만큼 반복한다는 뜻이다. 
    left = 0, //왼쪽 인덱스
    right = 0;  //오른쪽 인덱스
  let target; // 찾고자 하는 요소
  //일일이 번갈아가면서 비교하는방식(두 배열을 왔다갔다 한다.)
  while (cnt < k) { 
    if (arr1[left] < arr2[right]) { // arr1의 left보다 arr2의 right가 더 크다: target에 arr1[left] 할당. left 증가
      target = arr1[left];
      left++;
    } else {// arr1의 left보다 arr2의 right가 더 작다: target에 arr2[right] 할당. right 증가
      target = arr2[right];
      right++;
    }
    cnt++;
  }
  return target; //cnt가 K가 되었을 때, target 리턴.
};