Median of Two Sorted Arrays

binary-search • divide-and-conquer • array
Hard
O(log⁡(min(m,n)))O(\log(min(m,n)))

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Examples

Input
nums1 = [1, 3], nums2 = [2]
Output
2.0
The merged array is [1,2,3] and median is 2.
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.5
The merged array is [1,2,3,4] and median is (2+3)/2 = 2.5.

Solution

Do a binary search on the smaller array to partition both arrays so that left halves and right halves satisfy max(lefts) <= min(rights).
Adjust partition using binary search based on comparisons between partition elements.
When correct partition is found, compute median from neighboring elements. Time complexity is O(log⁡(min(m,n)))O(\log(min(m,n))).

Code Solution

median-two-arrays.ts
ts
1
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
2
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
3
  const m = nums1.length, n = nums2.length;
4
  let low = 0, high = m;
5
  while (low <= high) {
6
    const i = Math.floor((low + high) / 2);
7
    const j = Math.floor((m + n + 1) / 2) - i;
8


9
    const Aleft = i === 0 ? -Infinity : nums1[i - 1];
10
    const Aright = i === m ? Infinity : nums1[i];
11
    const Bleft = j === 0 ? -Infinity : nums2[j - 1];
12
    const Bright = j === n ? Infinity : nums2[j];
13


14
    if (Aleft <= Bright && Bleft <= Aright) {
15
      if ((m + n) % 2 === 0) {
16
        return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2;
17
      } else {
18
        return Math.max(Aleft, Bleft);
19
      }
20
    } else if (Aleft > Bright) {
21
      high = i - 1;
22
    } else {
23
      low = i + 1;
24
    }
25
  }
26
  throw new Error('Input arrays not sorted or invalid');
27
}