Median of Two Sorted Arrays: Binary Search on the Partition

This is the problem that separates people who use binary search from people who understand it. The prompt sounds tame — find the median of two sorted arrays — and the naive answer (merge them, pick the middle) is trivial. The catch is the required bound: O(log(min(m, n))). No merging allowed.

To hit that bound you stop thinking about individual elements and start thinking about a cut. The median is defined entirely by where you split the combined data into a smaller half and a larger half. Find that cut without ever building the merged array, and the median falls out of two boundary values.

Master this and you own the hardest flavor of binary search: searching over an abstract answer space instead of a literal array of values.

The problem#

Given two sorted arrays nums1 (length m) and nums2 (length n), return the median of the combined m + n elements. If the total count is odd, the median is the single middle value; if it's even, it's the average of the two middle values.

The arrays are already sorted. That ordering is the entire leverage — throw it away by re-sorting and you've lost the game before it starts.

The brute force baseline#

The obvious solution merges both arrays like the final step of merge sort, then reads off the middle.

This is correct and O(m + n) time, O(m + n) space. For most real use that's fine. But it touches every element, so it can never beat linear time — and the problem explicitly asks for logarithmic. The wasted work is obvious once you name it: you build the entire merged array just to look at one or two values in the middle. Everything else was busywork.

The key insight: partition, don't merge#

Forget merging. Imagine the final merged array split by a vertical line into a left half and a right half of equal size (or the left holding one extra element when the total is odd). If you could place that line correctly, the median lives right at it — no need to know the order of anything else.

Here's the reframe. A cut in the merged array corresponds to a cut in each input array. If you take i elements from the front of nums1 for the left half, then to keep the left half at exactly half the total, you must take a fixed number from nums2:

So the only free variable is i — how far into nums1 you cut. Choosing i determines j automatically. That's what makes this a binary search: you're searching for the one correct value of i in the range [0, m].

A cut is correct when everything on the left is <= everything on the right. You don't need to check all pairs, only the four boundary values around the two cuts:

The cut is valid exactly when maxLeftA <= minRightB and maxLeftB <= minRightA. Within each array the ordering is already guaranteed, so these two cross-checks are all that stand between you and the answer.

The optimal solution#

Binary search runs on the shorter array so the range stays [0, min(m, n)], which is what delivers O(log(min(m, n))). The first if guarantees that by swapping. Out-of-range boundaries use -Infinity / +Infinity sentinels so an empty side never breaks a comparison.

The three branches are the whole story. If both cross-checks pass, you're done: for an even total the median averages the two innermost boundary values; for an odd total the left half holds the extra element, so the median is just the largest value on the left. If maxLeftA > minRightB, nums1 gave the left half a value that's too big — pull the cut left with high = i - 1. Otherwise nums2's left boundary is too big, so push right with low = i + 1.

Walkthrough#

Trace nums1 = [1, 2], nums2 = [3, 4, 5, 6]. Since nums1 is shorter, no swap. m = 2, n = 4, total 6 (even), and (m + n + 1) / 2 = 3. Search starts at low = 0, high = 2.

Iteration 1 puts the cut at i = 1, so nums1's left is [1] and nums2's left is [3, 4]. But 4 (from nums2's left) exceeds 2 (nums1's right boundary) — the left half stole a value that belongs on the right. The fix is to take more from nums1, so low jumps to 2.

Iteration 2 cuts at i = 2, taking all of nums1 on the left (minRightA becomes +∞). Now left is {1, 2, 3}, right is {4, 5, 6}, and both cross-checks hold. Total is even, so the median averages the two innermost boundaries: max(maxLeftA=2, maxLeftB=3) = 3 and min(minRightA=+∞, minRightB=4) = 4, giving (3 + 4) / 2 = 3.5. Two iterations, no merge.

Complexity#

The optimal version searches over [0, min(m, n)] and halves that range every iteration, so it runs in logarithmic time relative to the shorter array. Space is constant — no merged array, just a handful of scalar boundaries. That's the entire payoff for thinking in cuts instead of elements.

Common mistakes#

• Searching the longer array. The bound is O(log(min(m, n))), not O(log(max)). Skip the initial length check and worst cases search the bigger array — still fast, but not the required bound, and j can go negative.
• Forgetting the ±Infinity sentinels. When i === 0 there is no maxLeftA, and when i === m there is no minRightA. Treating a missing boundary as 0 or undefined corrupts the comparisons. -Infinity on the left and +Infinity on the right make an empty side always satisfy the checks.
• Getting the half-size formula wrong. j = floor((m + n + 1) / 2) - i uses + 1 so that on an odd total the left half carries the extra element. That's exactly why the odd-case answer is max(maxLeftA, maxLeftB) with no averaging. Drop the + 1 and odd totals break.
• Off-by-one in the bound move. A failing left-cross means the cut is too far right, so high = i - 1; the other failure means too far left, so low = i + 1. Swapping these makes the search diverge or loop.
• Re-sorting the inputs. They arrive sorted. Sorting again is O(n log n) wasted work that also signals you missed the point of the problem.

Where this pattern shows up next#

Binary search on an answer that isn't a literal array index is the reusable skill here. It shows up whenever a monotonic yes/no decision lets you throw away half the search space:

• Binary Search — the base case: searching a value directly in one sorted array.
• Guess Number Higher or Lower — the same halving logic driven by a feedback oracle instead of array values.
• Sqrt(x) — binary searching a numeric answer range rather than array positions.
• Search in Rotated Sorted Array — deciding which half is sorted, then discarding the other.

You can also step through the partition search interactively to watch the cut slide, the four boundaries light up, and the search range collapse iteration by iteration.

FAQ#

Why binary search the shorter array instead of the longer one?#

Because the search range is [0, length] of whichever array you cut, and you want that range as small as possible to guarantee O(log(min(m, n))). Cutting the shorter array also keeps j = floor((m + n + 1) / 2) - i non-negative and within bounds. If you searched the longer array, j could compute to a negative index or one past the end of the shorter array, breaking the boundary lookups. The one-line swap at the top of the function enforces this before the loop ever runs.

What do the ±Infinity boundary values actually do?#

They stand in for the missing boundary when a cut sits at the very edge of an array. If the cut in nums1 is at index 0, there is no element to the left, so maxLeftA becomes -Infinity — a value smaller than anything real, which means it can never violate the "left <= right" check. Likewise, a cut at index m has no element to the right, so minRightA becomes +Infinity. These sentinels let one uniform comparison handle empty halves without a pile of special-case if statements.

How is the median read off once the partition is valid?#

Once both cross-checks pass, the left half holds the correct set of smallest elements. For an even total, the median is the average of the largest left value and the smallest right value: (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2. For an odd total, the + 1 in the half-size formula gives the left half one extra element, so the median is simply the largest value on the left — max(maxLeftA, maxLeftB) — with no averaging needed.

Why is this problem considered so much harder than a normal binary search?#

A standard binary search compares against a concrete value in the array and moves toward it. Here you're searching for an abstract cut point whose correctness depends on four boundary values across two arrays, plus edge handling for empty halves, plus a parity split between odd and even totals. Nothing you compare is the answer itself — you're binary searching a decision ("is this partition valid?") rather than a value. That extra layer of indirection is exactly why it lands in the Hard tier despite short code.