Median of Two Sorted Arrays

HardBinary SearchArrayBinary SearchDivide and Conquer

Problem

You are given two sorted arrays of integers, possibly of different lengths. Return the median of the combined set of all their values, as if the two arrays had been merged into one sorted array.

Example. For [1, 2] and [3, 4], the merged order is [1, 2, 3, 4], so the median is the average of the two middle values, 2 and 3, which is 2.5.

Key idea

Merging the two arrays and reading off the middle works, but costs time proportional to their combined length: more than is needed, since a median only requires knowing what lies on either side of one dividing point. The insight is to binary search directly for that dividing point, called a partition, without ever materializing the merge.

Pick a partition index in the shorter array, which fixes a matching partition in the longer array so the two together hold exactly half the elements on the left. A partition is correct when every element just left of the cut is no greater than every element just right of it, in both arrays. If the shorter array's left side is too large, move the partition left; otherwise move it right. Because shifting it changes those comparisons monotonically, the search converges quickly, and the median then comes directly from the boundary values.

Solution

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  const m = nums1.length;
  const n = nums2.length;
  // number of elements that belong on the left side of the combined split
  const leftSize = Math.floor((m + n + 1) / 2);

  let low = 0;
  let high = m;

  while (low <= high) {
    const cut1 = low + Math.floor((high - low) / 2);
    // cut2 is forced once cut1 is picked, so the left side always has leftSize elements
    const cut2 = leftSize - cut1;

    // treat a missing boundary as -Infinity or Infinity so it never wins or loses a comparison
    const leftMax1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
    const rightMin1 = cut1 === m ? Infinity : nums1[cut1];
    const leftMax2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
    const rightMin2 = cut2 === n ? Infinity : nums2[cut2];

    if (leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
      // both sides interleave correctly, this is the partition
      if ((m + n) % 2 === 0) {
        return (Math.max(leftMax1, leftMax2) + Math.min(rightMin1, rightMin2)) / 2;
      }
      return Math.max(leftMax1, leftMax2);
    } else if (leftMax1 > rightMin2) {
      // left side of the shorter array is too big, shift the cut left
      high = cut1 - 1;
    } else {
      low = cut1 + 1;
    }
  }

  throw new Error('Input arrays are not sorted');
}

Complexity

  • Time: O(log(min(n, m))). Binary search runs over the shorter array's index range.
  • Space: O(1). Only a handful of boundary values and indices are kept.

Watch out for

  • Binary search over the shorter array, not the longer one, or the partition math and edge-index bounds can go out of range.
  • Partitions at the very start or end of an array leave one side empty; treat that missing boundary as negative or positive infinity rather than a real value.

Pattern

This is binary search over a partition rather than a single value: the search narrows in on a split point defined by a cross-array balance condition, not a comparison to a fixed target. It is the sharpest example of turning a merge-like problem into a logarithmic search over the answer's structure.

Related questions