Median of Two Sorted Arrays

Two sorted arrays, find the median (or kth element) in O(log(m+n)). The required complexity is the giant hint. Merging is O(m+n) and too slow, so you binary search a PARTITION. This is the canonical "hard" binary search and a known filter question at top companies.

Merge the two arrays into one sorted array and take the middle element, or the average of the two middle elements when the total length is even.

O(m + n) time and O(m + n) space.

This is the right first answer and you should say it. The problem only becomes interesting because it demands O(log(m + n)), which forbids touching every element. Once linear is off the table, you are being told to search rather than scan, and the only question left is what you are searching for.

Stop looking for a value and start looking for a cut. Imagine slicing both arrays so that the pieces on the left, taken together, hold exactly half of all the elements. If additionally every element on the left is at most every element on the right, then you have found the median without ever merging anything. It is built from the two values sitting either side of the cut.

The two cuts are not independent. Once you choose how many elements to take from the first array, the count from the second is forced, because the total on the left is fixed at half. So there is really one number to search for, and it ranges from taking nothing to taking everything from the first array.

Checking a candidate cut is a pair of comparisons across the boundary: the largest on the left of A must not exceed the smallest on the right of B, and the same the other way round. If the first check fails you took too much from A, so slide the cut left. If the second fails you took too little, so slide right. Always binary search the shorter array, which both bounds the work at O(log min(m, n)) and keeps the derived cut inside the longer one.

def findMedianSortedArrays(a, b):
    if len(a) > len(b):
        a, b = b, a                       # binary search smaller array
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2                # cut in a
        j = half - i                      # matching cut in b
        aL = a[i-1] if i > 0 else float('-inf')
        aR = a[i]   if i < m else float('inf')
        bL = b[j-1] if j > 0 else float('-inf')
        bR = b[j]   if j < n else float('inf')
        if aL <= bR and bL <= aR:         # correct partition
            if (m + n) % 2:
                return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        elif aL > bR:
            hi = i - 1                     # move cut i left
        else:
            lo = i + 1                     # move cut i right

Treat a cut at either edge as negative infinity on the left or positive infinity on the right. That removes every boundary special case and lets the two comparisons stand unguarded, which is the difference between this being writable under pressure and not.

The parity of the combined length is handled once, at the end. For an odd total the median is the larger of the two left-hand values, and for an even total it is the average of that and the smaller of the two right-hand values.

The loop searches over counts, from 0 to the length of the shorter array inclusive, rather than over indices. Mixing those two mental models is the usual reason this solution fails on the first attempt.