Problem. Given two sorted arrays a (length m) and b (length n), return the median of all m + n values, in
O(log(m + n)).
a = [1, 3], b = [2] → 2.0
a = [1, 2], b = [3, 4] → 2.5 ((2 + 3) / 2)
a = [], b = [5] → 5.0
The median splits the combined values into a left half and a right half of equal size (the left gets one extra when the total is odd), with every left value ≤ every right value. We never need to build the combined array: we only need to find where that split falls in each array.
ML context. Medians and percentiles are the honest summaries of latency and loss (a mean hides the slow tail). Logs are often already sorted per shard: per-server latencies, per-day scores. Combining two sorted summaries into one percentile without merging them is this problem; across many shards it becomes a search on the value (Change B), and at real scale an approximate sketch (Change D).