Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log min(m, n)) by binary searching where to cut the shorter array.
Problem Understanding
Median of Two Sorted Arrays: given two sorted arrays nums1 and nums2, return the median of all their numbers together, in O(log(m + n)) time.
Examples: [1, 3] and [2] give 2.0; [1, 2] and [3, 4] give (2 + 3) / 2 = 2.5.
Attempt 1: Merge, Then Pick the Middle
Merge the arrays as in Merge Two Sorted Lists and take the middle one or two values. That is O(m + n), and you only need to merge halfway, but it is still linear. The required log time means binary search, and the trick is choosing what to search.
The Intuition: Search the Cut, Not a Value
The median splits all the numbers into a smaller half and a larger half. Make that split with one cut in each array: take i numbers from A and j from B, with i + j = half, where half = (m + n + 1) / 2.
Once i is chosen, j is fixed. The cut is correct when every left number is ≤ every right number. Within each array that is already true, so only two cross checks remain:
A[i−1] ≤ B[j]andB[j−1] ≤ A[i](treat values off the ends as −∞ or +∞).
If A[i−1] > B[j], too much was taken from A: move the cut left. If B[j−1] > A[i], too little: move it right. That monotone choice is exactly what binary search needs. On a valid cut, the median is the largest left value (odd total) or the average of the largest left and smallest right values (even total).
Interactive Walkthrough
Each array is drawn with a bar at its cut, and everything left of the bars is shaded: together, half of all the numbers. The four values touching the bars are the only ones compared; watch the cut in A move until both checks pass.
Dry Run Table
Input: nums1 = [3, 4], nums2 = [1, 2]. A = [3, 4], B = [1, 2], half = 2.
| lo | hi | i | j | A[i−1] | A[i] | B[j−1] | B[j] | Result |
|---|---|---|---|---|---|---|
| 0 | 2 | 1 | 1 | 3 | 4 | 1 | 2 | 3 > 2: hi = 0 |
| 0 | 0 | 0 | 2 | −∞ | 3 | 2 | +∞ | valid |
Even total: (max(−∞, 2) + min(3, +∞)) / 2 = 2.5.
The Solution Template
Binary search the cut in the shorter array.
Median of Two Sorted Arrays Code
1var findMedianSortedArrays = function(nums1, nums2) {2 if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];3 const A = nums1, B = nums2;4 const total = A.length + B.length, half = (total + 1) >> 1;5 let lo = 0, hi = A.length;6 while (lo <= hi) {7 const i = (lo + hi) >> 1, j = half - i;8 const aLeft = i > 0 ? A[i - 1] : -Infinity;9 const aRight = i < A.length ? A[i] : Infinity;10 const bLeft = j > 0 ? B[j - 1] : -Infinity;11 const bRight = j < B.length ? B[j] : Infinity;12 if (aLeft <= bRight && bLeft <= aRight) {13 if (total % 2) return Math.max(aLeft, bLeft);14 return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;15 }16 if (aLeft > bRight) hi = i - 1;17 else lo = i + 1;18 }19};
Edge Cases & Common Mistakes
- One empty array: the search over the empty array has only i = 0, and the median comes from the other array.
- Searching the longer array: j can go negative or past the end; always search the shorter one.
- Forgetting the sentinels: a cut at either end has no neighbour on one side; use −∞ and +∞.
- Odd totals: with half = (m + n + 1) / 2, the left side holds the extra element, so the median is the largest left value.
Summary
Cut the shorter array after i elements and the other after half − i. The cut is valid when A[i−1] ≤ B[j] and B[j−1] ≤ A[i]; otherwise move it left or right by binary search. The median comes from the four values around the cut. O(log min(m, n)) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet