Median of Two Sorted Arrays

1. Define the problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)) . Rather than merging the arrays, binary search for a partition of the smaller array such that every element to its left, combined with the matching partition of the other array, is no bigger than every element to the right.

Constraints

nums1.length == m
nums2.length == n
0 ≤ m ≤ 1000
0 ≤ n ≤ 1000
1 ≤ m + n ≤ 2000
-10⁶ ≤ nums1_i, nums2_i ≤ 10⁶

Example

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

Output2.00000

Explanation The merged array is [1, 2, 3], and its median is 2.

2. Know the words first

In plain terms

Partition: A single cut through an array that splits it into a left part and a right part — here, cuts through both arrays together split all the combined values into a correctly sized left half and right half.

3. Visualize the solution

Binary search the smaller array for a valid partition

A02

B01

B13

Statusguess

Searching the shorter array [2] with partition i=0: left edge -∞, right edge 2. In [1, 3], j=2 lands the matching partition with left edge 3, right edge ∞. 3 > 2, so the guess needs to shift. The box shows which elements this guess puts on the left side: B0 and B1.

What happens in this step

a=[2] (shorter, m=1), b=[1,3] (n=2), half=floor((1+2+1)/2)=2
i = 0 + floor((1-0)/2) = 0, j = half - i = 2

leftA = -∞ (i=0), rightA = a[0] = 2
leftB = b[j-1] = b[1] = 3, rightB = ∞ (j=n)

leftB (3) > rightA (2) — B's left side reaches past A's right side, so this partition is too far left. low moves to i + 1 = 1.

Step 1 of 3

Steps to visualize

The row holds every element of both arrays: A first, then B. The box marks the elements the current guess puts on the left side of the split.
Always binary search over the shorter of the two arrays, to keep the search space small.
Guess a partition index i in the shorter array; the matching partition j in the other array is fixed by how many elements the left side needs in total.
Compare the edge values across the two partitions: if the left side of one array is bigger than the right side of the other, the guess is off.
If the left edge of array one exceeds the right edge of array two, the partition needs to move left; otherwise move it right.
When both cross-edges line up correctly, the median is computed directly from the four edge values.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Binary search the smaller array for a valid partition

A02

B01

B13

Statusguess

What happens in this step

a=[2] (shorter, m=1), b=[1,3] (n=2), half=floor((1+2+1)/2)=2
i = 0 + floor((1-0)/2) = 0, j = half - i = 2

leftA = -∞ (i=0), rightA = a[0] = 2
leftB = b[j-1] = b[1] = 3, rightB = ∞ (j=n)

leftB (3) > rightA (2) — B's left side reaches past A's right side, so this partition is too far left. low moves to i + 1 = 1.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function findMedianSortedArrays(nums1, nums2) {
  let a = nums1;
  let b = nums2;

  if (a.length > b.length) {
    const temp = a;
    a = b;
    b = temp;
  }

  const m = a.length;
  const n = b.length;
  const half = Math.floor((m + n + 1) / 2);

  let low = 0;
  let high = m;

  while (low <= high) {
    const i = low + Math.floor((high - low) / 2);
    const j = half - 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 === 0) {
        return (Math.max(leftA, leftB) + Math.min(rightA, rightB)) / 2;
      }
      return Math.max(leftA, leftB);
    } else if (leftA > rightB) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }

  return 0;
}

Time: O(log(min(m, n)))
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums1 = [1, 3], nums2 = [2]`	`2`	example from the docstring, odd combined length
`nums1 = [1, 2], nums2 = [3, 4]`	`2.5`	even combined length, median averages the two middle values
`nums1 = [], nums2 = [1]`	`1`	one array is empty
`nums1 = [2], nums2 = []`	`2`	the other array is empty, and the longer one is passed first
`nums1 = [1, 2], nums2 = [1, 2]`	`1.5`	two identical sorted arrays
`nums1 = [1], nums2 = [2]`	`1.5`	smallest non-trivial input, one element each
`nums1 = [1, 3, 5, 7, 9], nums2 = [2, 4, 6]`	`4.5`	arrays of noticeably different lengths, even combined length

Median of Two Sorted Arrays