Median of Two Sorted Arrays

The machine must find the median of two sorted arrays in O(log(min(m,n))). Merging is O(m+n) — correct but too slow. The insight: the median is a cut. Cut both arrays so the left halves hold exactly the same count of elements and every left element is ≤ every right element; then the median derives from the four elements at the cuts. Binary search the cut position in the smaller array; the other cut is then determined.

def find_median_sorted_arrays(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2
        j = (m + n + 1) // 2 - i
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

Steps: (1) binary search the cut in the smaller array, (2) derive the second cut from the total length, (3) check the cross conditions; when they hold, compute the median from the boundary elements.

Time is O(log(min(m,n))). Space is O(1). The ±inf sentinels handle cuts at the edges.

Trickiest edge case: an empty array — sentinels carry the comparisons, and j must stay in bounds. Even vs odd total length changes which elements combine. Duplicates at the cut boundaries are fine; only the ≤ conditions matter.