47. Median of Two Ranked Sources

Problem

Fin's retrieval layer sometimes queries two independent sources for a single query (say, a first-party knowledge base and a partner-provided article index) and each source returns its own results already sorted by relevance score, ascending. To sanity-check the combined result distribution without paying the cost of a full merge, compute the median relevance score across the union of both sorted lists directly.

Given two sorted arrays a and b of possibly different lengths, return the median value of the merged, still-sorted sequence — without actually building the merged array. The target time complexity is O(log(min(len(a), len(b)))).

Source: src/47_median_of_two_ranked_sources.py

def median_two_sorted(a: list[float], b: list[float]) -> float:

>>> median_two_sorted(a=[1, 3], b=[2])
2.0

>>> median_two_sorted(a=[1, 2], b=[3, 4])
2.5

Step-by-Step Approach

1. Always binary search over the shorter of the two arrays — swap a and b if a is longer, so the search space is as small as possible.
2. The goal is to find a "partition" index i in the shorter array (a) and a corresponding partition index j in the longer array (b) such that the left halves combined contain exactly half = (n + m + 1) // 2 elements, where n, m are the two lengths.
3. For a candidate i, compute j = half - i so the split is always balanced. Look at the boundary elements: a_left, a_right around index i in a, and b_left, b_right around index j in b (using -inf/inf sentinels at the array edges).
4. The partition is correct when a_left <= b_right and b_left <= a_right — every element to the left of the partition is <= every element to the right of it, across both arrays combined.
5. If a_left > b_right, i is too far right — move the binary search boundary left (hi = i - 1). Otherwise move it right (lo = i + 1).
6. Once the correct partition is found: if the combined length is odd, the median is max(a_left, b_left). If even, it's the average of max(a_left, b_left) and min(a_right, b_right).

The key insight is that you never need to materialize the merge — you only need to find the split point where the correct number of elements land on each side, and binary search converges on that split in log time.

Reference solution

def median_two_sorted(a: list[float], b: list[float]) -> float:
    # binary search the partition point on the shorter array, O(log(min(len(a), len(b))))
    if len(a) > len(b):
        # swap so binary search always runs on the shorter array
        a, b = b, a
    n, m = len(a), len(b)
    lo, hi = 0, n
    # left-half size; works for both odd and even totals
    half = (n + m + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2
        # matching split index in b, derived from i (only one search needed)
        j = half - i
        # -inf/inf sentinels for out-of-bounds edges
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < n else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < m else float("inf")
        # correct partition: every left <= every right
        if a_left <= b_right and b_left <= a_right:
            if (n + m) % 2 == 1:
                # odd total: median is the larger left boundary
                return float(max(a_left, b_left))
            # even: avg largest-left/smallest-right
            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        if a_left > b_right:
            # a's left too big, move partition left
            hi = i - 1
        else:
            # otherwise move partition right
            lo = i + 1
    raise ValueError("Input arrays must be sorted")

Key Functions & Tricks

• float("-inf") / float("inf") — sentinel values for boundary elements that fall off an array's edge.
• if len(a) > len(b): a, b = b, a — swap so the binary search always runs on the shorter array.
• Partition-point binary search — search a split i in the shorter array instead of merging, O(log(min(n, m))).
• half = (n + m + 1) // 2 — left-half size, correct for both odd and even combined totals.
• a_left <= b_right and b_left <= a_right — correct-partition test across both arrays.
• Binary search direction — shrink/grow hi/lo toward the correct partition i.
• raise ValueError(...) — defensive fallback if the inputs weren't actually sorted.

How to Recognize This Pattern