Median of Two Sorted Arrays: The Partition Search

This one is a Hard-rated classic reported from Google, Amazon, Apple interviews: "Median of Two Sorted Arrays". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Modified Binary Search pattern on sight. Part 11 of 11 in the Modified Binary Search arc.

The Problem

Given two sorted arrays of sizes m and n, return the median of their union in O(log(m + n)). The most famous hard question in the binary search canon. Merging is O(m + n) and scores partial credit at best — the intended answer searches partitions, not elements.

Input:  nums1 = [1, 3], nums2 = [2]
Output: 2.0
For nums1 = [1, 2], nums2 = [3, 4] the answer is 2.5.

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

The median splits the union into equal halves where everything left is at most everything right. Choosing i elements from array A forces choosing half-minus-i from array B — one degree of freedom — and validity of a split is monotonic in i. One-dimensional monotonic feasibility: binary search, on the smaller array.

The Approach

Binary search the cut position i in the smaller array; j is determined. The cut is correct when A's left max is at most B's right min and vice versa. Too-big left max on A's side moves the cut left; otherwise right. Sentinel infinities handle cuts at the edges without special cases.

From a correct cut, the median reads off the boundary values — max of lefts for odd totals, average of the two middles for even. Practice this one on paper until the invariant is muscle memory; it is a different search shape than everything before it.

Python Solution

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    """Median of two sorted arrays in O(log min(m, n))."""
    a, b = (nums1, nums2) if len(nums1) <= len(nums2) else (nums2, nums1)
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    INF = float("inf")

    lo, hi = 0, m
    while True:
        i = (lo + hi) // 2             # elements taken from a's left
        j = half - i                   # forced take from b's left
        a_left = a[i - 1] if i > 0 else -INF
        a_right = a[i] if i < m else INF
        b_left = b[j - 1] if j > 0 else -INF
        b_right = b[j] if j < n else INF

        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        if a_left > b_right:
            hi = i - 1                 # took too many from a
        else:
            lo = i + 1                 # took too few from a

Complexity

• Time: O(log min(m, n)) — the cut position in the smaller array is halved each step
• Space: O(1) — boundary variables and sentinels

Interview Tips and Follow-Ups

• Searching the smaller array is not a micro-optimization — it guarantees j stays in range. Skip it and empty-array cases explode.
• The half = (m + n + 1) // 2 ceiling unifies odd and even totals — derive it once rather than memorizing two cases.
• Generalization: k-th smallest of two sorted arrays — same partition logic with half replaced by k. If you truly own this, that follow-up is free.

More Modified Binary Search problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.