Median of Two Sorted Arrays
Return the median of two sorted arrays in O(log(min(n,m))).
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10⁶ <= nums1[i], nums2[i] <= 10⁶
Intuition
Median of two sorted arrays asks for the median of the combined arrays in O(log(min(n, m))). Merging them is O(n + m) and already feels efficient, so the logarithmic requirement is what forces a completely different idea.
Stop thinking about merging and think about cutting. The median splits the union into two halves of equal size where everything on the left is at most everything on the right. So choose a cut in A after i elements and a cut in B after j elements, with the left parts together holding exactly half the union:
- i + j = (n + m + 1) / 2 — so choosing i forces j, leaving only one unknown to search.
The +1 in that formula makes the left half take the extra element on an odd total, which is what puts the median at the end of the left half rather than the start of the right.
A cut is correct when neither side reaches across the other:
- A[i−1] ≤ B[j] and B[j−1] ≤ A[i].
If A[i−1] > B[j], the cut in A is too far right — search lower. That comparison is monotone in i, which is what makes binary search valid.
Once a valid cut is found, the median comes straight from the boundary values: for an odd total it is the maximum of the two left-side elements; for an even total it is the average of that and the minimum of the two right-side elements. Use ±∞ sentinels for cuts at the array edges so no special cases are needed, and always binary search the shorter array.
When a problem demands better than O(n) on sorted input, you're binary searching something — and it isn't always the answer directly. Here you search over the partition point: how many elements of the smaller array fall on the left side. The median only needs the four values straddling that cut, never the merged array itself. Binary-searching a decision rather than a value is the move that also cracks split-array-largest-sum and koko-eating-bananas.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(log min(n,m)) time and O(1) space.
Cut both arrays instead of merging
A cut after i elements of A and j of B splits the union into two halves. The median is determined entirely by the four values adjacent to the cuts, so no element-by-element merge is ever required.
Force j from i
Set j = (n + m + 1) / 2 - i, so the left halves always hold exactly half the union. This reduces the search to one variable, and the +1 puts the extra element on the left for odd totals — which is where the median then sits.
Test the cut with two comparisons
The cut is valid when A[i-1] <= B[j] and B[j-1] <= A[i]. Each condition says one side does not reach across the other. If A[i-1] > B[j], i is too large — move the search window down.
Use infinities at the edges
When a cut sits at index 0 or at the end of an array, one of the four values does not exist. Treat a missing left value as −∞ and a missing right value as +∞ — the comparisons then work unmodified instead of needing four special cases.
Binary search the shorter array
Search i from 0 to n on the smaller array, swapping the two if necessary. This bounds the iteration count at O(log min(n, m)), which is the requirement the problem sets.
Read the median from the boundary
For an odd total, the median is max(A[i-1], B[j-1]). For an even total it is the average of that and min(A[i], B[j]). Average as a float — integer division here is a common wrong answer on even-length inputs.
Cost of the cut search
O(log min(n, m)) time and O(1) space, against O(n + m) for merging. The saving matters when both arrays are large, and this is the generalisation of the Kth Element problem with k fixed at the midpoint.
Solution & live demo
Common pitfalls
Binary searching the larger array
lo, hi = 0, len(b)
if len(a) > len(b): a, b = b, a lo, hi = 0, len(a)
j = half - i can then fall outside the other array's bounds, producing negative or oversized indices. Searching the shorter side keeps j legal for every i and pins the complexity to O(log min(m, n)).
Guarding the edges with real array values
a_left = a[i-1] if i > 0 else a[0]
a_left = a[i-1] if i > 0 else -INF
An empty left partition must never lose a comparison, and an empty right partition must never win one — that's precisely what the infinities encode. Substituting a real element makes the cut appear invalid and the search never converges.
Integer division on the final average
return (max(a_left, b_left) + min(a_right, b_right)) // 2
return (max(a_left, b_left) + min(a_right, b_right)) / 2
The median of an even-length set is genuinely fractional — [1, 2, 3, 4] gives 2.5. Floor division truncates it to 2.
Edge cases
Cut takes 0 from it; sentinels handle every comparison — median of the other array.
Search pushes i to n; sentinel +∞ on A's right keeps checks valid.