Median of two sorted arrays
Problem
Given two sorted arrays of sizes m and n, return the median of all m + n values combined. With an even total, the median is the average of the two middle values. The target is O(log(min(m, n))) time.
Example 1
Input: a = [1, 3], b = [2] Output: 2
Example 2
Input: a = [1, 2], b = [3, 4] Output: 2.5
Merged [1, 2, 3, 4]: (2 + 3) / 2.
Also asked as: Median of 2 sorted arrays of equal size · Median of 2 sorted arrays of different size
Test cases
Case 1
Input: [1,3], [2] Expected: 2
Case 2
Input: [1,2], [3,4] Expected: 2.5
Case 3
Input: [], [1] Expected: 1
View solutionHide solution1 approach
1. Binary search on the partition of the smaller array
Time O(log min(n, m))Space O(1)
Choose how many of the first array go in the left half; derive the count from the second. Slide until maxLeft ≤ minRight on both sides.
function findMedianSortedArrays(a, b) { if (a.length > b.length) [a, b] = [b, a]; const n = a.length, m = b.length, half = (n + m + 1) >> 1; let lo = 0, hi = n; while (lo <= hi) { const i = (lo + hi) >> 1; // from a const j = half - i; // from b const aLeft = i > 0 ? a[i - 1] : -Infinity; const aRight = i < n ? a[i] : Infinity; const bLeft = j > 0 ? b[j - 1] : -Infinity; const bRight = j < m ? b[j] : Infinity; if (aLeft <= bRight && bLeft <= aRight) { if ((n + m) % 2) return Math.max(aLeft, bLeft); return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2; } if (aLeft > bRight) hi = i - 1; else lo = i + 1; } throw new Error('inputs not sorted');}