Binary Search on Two Arrays

Description

This skill finds the k-th smallest element, or the median, of two sorted arrays without merging them. Merging takes O(n + m) time and memory just to read one position. But the answer is decided by how many of the first k elements come from each array. Once you pick how many come from the first, the second array's share is fixed. That turns a two-array question into a binary search over one number, the cut in the shorter array.

We'll go from simple to more technical:

1. The pattern: binary search the cut in the shorter array, with sentinels at the edges.
2. A second flavor: the median, for odd and even totals.
3. Where rank-based splitting shows up (merging shards, distributed quantiles).
4. What breaks it: searching the longer array, missing sentinels, merging anyway.

The approach

int kthElement(int[] a, int[] b, int k) {             // a is the shorter array
    if (a.length > b.length) return kthElement(b, a, k);
    int lo = Math.max(0, k - b.length), hi = Math.min(k, a.length);
    while (lo <= hi) {
        int cutA = lo + (hi - lo) / 2;                 // take cutA elements from a...
        int cutB = k - cutA;                           // ...so the rest must come from b
        int leftA  = cutA == 0 ? Integer.MIN_VALUE : a[cutA - 1];
        int leftB  = cutB == 0 ? Integer.MIN_VALUE : b[cutB - 1];
        int rightA = cutA == a.length ? Integer.MAX_VALUE : a[cutA];
        int rightB = cutB == b.length ? Integer.MAX_VALUE : b[cutB];
        if (leftA <= rightB && leftB <= rightA) return Math.max(leftA, leftB);   // a valid split
        if (leftA > rightB) hi = cutA - 1;             // took too many from a
        else lo = cutA + 1;                            // took too few from a
    }
    return -1;                                         // unreachable for valid k
}

def kth_element(a: list[int], b: list[int], k: int) -> int:   # a is the shorter array
    if len(a) > len(b):
        return kth_element(b, a, k)
    lo, hi = max(0, k - len(b)), min(k, len(a))
    while lo <= hi:
        cut_a = (lo + hi) // 2                     # take cut_a elements from a...
        cut_b = k - cut_a                          # ...so the rest must come from b
        left_a = a[cut_a - 1] if cut_a > 0 else float("-inf")   # a[-1] would be the LAST element
        left_b = b[cut_b - 1] if cut_b > 0 else float("-inf")
        right_a = a[cut_a] if cut_a < len(a) else float("inf")
        right_b = b[cut_b] if cut_b < len(b) else float("inf")
        if left_a <= right_b and left_b <= right_a:
            return max(left_a, left_b)             # a valid split
        if left_a > right_b:
            hi = cut_a - 1                         # took too many from a
        else:
            lo = cut_a + 1                         # took too few from a
    return -1                                      # unreachable for valid k

A split is correct when everything on the left of both cuts is <= everything on the right - then the left side holds exactly the k smallest values, and the k-th is the larger of the two left edges. If a's left edge is too big, fewer elements should come from a; if b's is too big, more should. The bounds keep cutB within b: at least k - b.length elements must come from a, and at most min(k, a.length) can.

A second flavor: the median

The median is the same search with k = (n + m + 1) / 2, the size of the left half. With an odd total, the median is the largest left element; with an even total, it's the average of the largest left element and the smallest right element:

// at a valid split with k = (n + m + 1) / 2:
double median = ((n + m) % 2 == 1)
        ? Math.max(leftA, leftB)
        : (Math.max(leftA, leftB) + (double) Math.min(rightA, rightB)) / 2.0;

# at a valid split with k = (n + m + 1) // 2:
median = (max(left_a, left_b) if (n + m) % 2 == 1
          else (max(left_a, left_b) + min(right_a, right_b)) / 2)   # / is true division

For [1, 3] and [2] that's 2.0; for [1, 2] and [3, 4], (2 + 3) / 2 = 2.5. Converting to double before adding avoids overflowing two large ints. (In Python, ints can't overflow and / always divides exactly - // would floor 2.5 to 2.)

Where you'll see it

Distributed databases and analytics engines compute percentiles and top-k across shards that are each sorted, without shipping and merging all the data; the same "how many from each side" split generalizes to k sorted sources (with a binary search over the value instead of the count). External sorting and merge-based query plans rely on the same reasoning about ranks across sorted runs.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why is it enough to binary-search only one array's cut?

2. What makes a split valid, and what's the k-th element then?

3. How does the median follow from the same search?

Key takeaways

• Choosing how many of the first k come from one array fixes the other array's share.
• Binary-search the shorter array's cut, with bounds max(0, k - m) to min(k, n).
• Valid split: both left edges <= both right edges; the k-th element is the larger left edge.
• Sentinels (MIN_VALUE, MAX_VALUE) handle empty sides without special cases.
• The median is the same search with k = (n + m + 1) / 2, plus the odd/even rule.