Median of two sorted arrays

Hard TimeO(log min(n, m)) SpaceO(1)

The median is the middle value once everything is in order, or the average of the two middle values when the count is even. Given two arrays a and b, each already sorted ascending, return the median of all their values combined. Either may be empty, but not both.

Examples

Example 1

Input
a = [1, 3]b = [2, 4]
Output
2.5
Together they are 1, 2, 3, 4; the two middle values average to (2 + 3) / 2.

Example 2

Input
a = [1, 3]b = [2]
Output
2
Together they are 1, 2, 3 — an odd count, so the middle value is the median.

The Code

function findMedianSortedArrays(a, b) {
  if (a.length > b.length) return findMedianSortedArrays(b, a);
  const m = a.length;
  const n = b.length;
  let low = 0;
  let high = m;
  while (low <= high) {
    const i = Math.floor((low + high) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const leftA = i === 0 ? -Infinity : a[i - 1];
    const rightA = i === m ? Infinity : a[i];
    const leftB = j === 0 ? -Infinity : b[j - 1];
    const rightB = j === n ? Infinity : b[j];
    if (leftA <= rightB && leftB <= rightA) {
      if ((m + n) % 2 === 1) return Math.max(leftA, leftB);
      return (Math.max(leftA, leftB) + Math.min(rightA, rightB)) / 2;
    }
    if (leftA > rightB) high = i - 1;
    else low = i + 1;
  }
  return 0;
}
findMedianSortedArrays([1, 3], [2, 4]);
Done
Step through findMedianSortedArrays([1, 3], [2, 4]) call by call

More like this

All searching examples (8) →