11. Median of Two Sorted Arrays

Problem

A distributed eval run splits its prompt set across two workers. Each worker scores its own shard and returns the scores already sorted ascending. To sanity-check the combined score distribution without paying the cost of concatenating and re-sorting both shards, compute the median score across the union of the two sorted lists directly — in O(log(min(m, n))) time, not the O(m + n) a full merge would cost.

Source: src/11_median_of_two_sorted_arrays.py

def find_median_sorted_arrays(nums1: list[float], nums2: list[float]) -> float: ...

>>> find_median_sorted_arrays([1, 3], [2])
2.0

>>> find_median_sorted_arrays([1, 2], [3, 4])
2.5

Step-by-Step Approach

1. Always binary-search the partition point on the SHORTER of the two arrays — this is what bounds the runtime by log(min(m, n)) instead of log(max(m, n)). Swap the arrays up front if needed.
2. A valid "partition" splits the combined array into a left half and a right half of (near-)equal size, where every element in the left half is <= every element in the right half. Once found, the median is derivable directly from the four elements straddling the two individual cut points.
3. For a candidate cut i in the shorter array, the cut j in the longer array is forced: it must make the combined left half exactly (m + n + 1) // 2 elements, so j = half - i.
4. Binary search i over [0, m]. At each step compute the four boundary values (left1, right1, left2, right2), using -inf/+inf sentinels when a cut lands at an array's edge.
5. If left1 <= right2 and left2 <= right1, the partition is valid: for odd total length the median is max(left1, left2); for even length it's the average of max(left1, left2) and min(right1, right2).
6. Otherwise, if left1 > right2, the shorter array's left half is too big — shrink the search range downward; if left2 > right1, it's too small — grow it upward. Repeat until a valid partition is found.

The key insight is that you never need to actually merge anything: the median only depends on the four values immediately adjacent to a correctly-placed pair of cut points, and binary search finds that pair directly by treating "is this partition balanced?" as a monotonic yes/no question over the shorter array's cut position.

Reference solution

def find_median_sorted_arrays(nums1: list[float], nums2: list[float]) -> float:
    # binary search the partition point on the SHORTER array; the partition on
    # the longer array is then forced by the total-length split, O(log(min(m, n)))
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    total = m + n
    half = (total + 1) // 2  # size of the combined left half

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2  # elements of nums1 in the left half
        j = half - i  # elements of nums2 in the left half, forced by i

        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")

        if left1 <= right2 and left2 <= right1:
            # valid partition: every left element <= every right element
            if total % 2 == 1:
                return float(max(left1, left2))
            return (max(left1, left2) + min(right1, right2)) / 2.0
        elif left1 > right2:
            hi = i - 1  # nums1's left half is too big, shrink it
        else:
            lo = i + 1  # nums1's left half is too small, grow it

    raise ValueError("input arrays are not sorted")

Key Functions & Tricks

• Binary search on the shorter array only — the fundamental trick that gets the runtime to O(log(min(m, n))) instead of a linear or O(log(m+n)) approach.
• j = half - i — the forced-partner-cut trick; only one array's cut needs to be searched because the other is fully determined by the total split size.
• float("-inf") / float("inf") sentinels — let edge cuts (all-left or all-right) be handled with the same comparison logic as interior cuts.
• total % 2 branch — odd-length combined arrays have a single middle element; even-length ones average the two middle elements.
• Adjusting lo/hi based on which side is "too big" — standard binary-search-on-the-answer shrink/grow logic.

How to Recognize This Pattern