4. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2, return the median of the two arrays combined. The overall run time should be O(log(m + n)).

Cut both arrays so the left halves together hold half the elements. Binary-search the cut in the shorter array until every left value is ≤ every right value; the median sits at the cut.

1function findMedianSortedArrays(a: number[], b: number[]): number {
2  if (a.length > b.length) [a, b] = [b, a];
3  const m = a.length, n = b.length, half = (m + n + 1) >> 1;
4  let lo = 0, hi = m;
5  while (lo <= hi) {
6    const i = (lo + hi) >> 1, j = half - i;
7    const aL = i ? a[i - 1] : -Infinity, aR = i < m ? a[i] : Infinity;
8    const bL = j ? b[j - 1] : -Infinity, bR = j < n ? b[j] : Infinity;
9    if (aL <= bR && bL <= aR)
10      return (m + n) % 2 ? Math.max(aL, bL) : (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
11    if (aL > bR) hi = i - 1;
12    else lo = i + 1;
13  }
14  return 0;
15}

lo = 0hi = 5half = 6

shorter (a)

longer (b)

Binary search the cut in a over [0, 5]. Left halves must hold 6 values.

1 / 0

Space: play/pause · ←/→: step