Median of Two Sorted Arrays

binary.ts

function medianOfTwoSorted(sortedA: Array<number>, sortedB: Array<number>) {
  let [m, n] = [sortedA.length, sortedB.length];

  if (m > n) {
    // Use the longest array for m.
    [sortedA, sortedB, m, n] = [sortedB, sortedA, n, m];
  }

  if (n === 0) {
    throw new Error('Array should not be empty');
  }

  let [iMin, iMax, halfLength] = [0, m, Math.floor((m + n + 1) / 2)];

  while (iMin <= iMax) {
    let i = Math.floor((iMin + iMax) / 2);
    let j = halfLength - i;

    if (i < m && sortedB[j - 1] > sortedA[i]) {
      iMin = i + 1;
      continue;
    }

    if (i > 0 && sortedA[i - 1] > sortedB[j]) {
      iMax = i - 1;
      continue;
    }

    let maxOfLeft =
      i === 0
        ? sortedB[j - 1]
        : j === 0
        ? sortedA[i - 1]
        : Math.max(sortedA[i - 1], sortedB[j - 1]);

    if ((m + n) % 2 === 1) {
      return maxOfLeft;
    }

    let minOfRight =
      i === m
        ? sortedB[j]
        : j === n
        ? sortedA[i]
        : Math.min(sortedA[i], sortedB[j]);

    return (maxOfLeft + minOfRight) / 2;
  }
}

problem.txt

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5