K-th Element From Two Sorted Arrays

Problem Statement

Find the k-th element of two sorted arrays. The arrays are 0-indexed.
The following visualisation shows the process of finding the k-th element by narrowing down the search space.
The search space is narrowed down by comparing the middle elements of the two arrays.
The search space is narrowed down to the left or right of the middle elements based on the comparison of the middle elements.
The search space is narrowed down until the k-th element is found.

Solution After Merging Array:

Merged

Stages of Binary Search

Stage 1

Stage 2

Stage 3

Stage 4

Result

Final

Solution


function findKthElement(A, B, k, a_start, a_end, b_start, b_end) {
  if (a_start > a_end) {
    return { array: B, position: k - a_start };
  }
  if (b_start > b_end) {
    return { array: A, position: k - b_start };
  }
  let a_mid = Math.floor((a_start + a_end) / 2);
  let b_mid = Math.floor((b_start + b_end) / 2);

  let a = A[a_mid];
  let b = B[b_mid];

  if (a_mid + b_mid < k) {
    if (a < b) {
      return findKthElement(A, B, k, a_mid + 1, a_end, b_start, b_end);
    } else {
      return findKthElement(A, B, k, a_start, a_end, b_mid + 1, b_end);
    }
  } else {
    if (a < b) {
      return findKthElement(A, B, k, a_start, a_end, b_start, b_mid - 1);
    } else {
      return findKthElement(A, B, k, a_start, a_mid - 1, b_start, b_end);
    }
  }
}

function solve(A, B, k) {
  let n = A.length;
  let m = B.length;
  // k is 0-indexed
  let result = findKthElement(A, B, k - 1, 0, n - 1, 0, m - 1);
  return { result };
}

Umakant Vashishtha