Median of Two Sorted Arrays: Binary Search Partition, O(log min(m,n))

• Median of Two Sorted Arrays – finds the median of the combined sorted order of two already-sorted arrays without merging them.
• Partition search – binary-search a cut in the smaller array; the matching cut in the larger array is derived so the left side holds half the total elements.
• Crossing condition – maxLeftA <= minRightB and maxLeftB <= minRightA must both hold for a valid split.
• O(log min(m, n)) time, O(1) space – searching the smaller array keeps the tightest bound.
• Infinity sentinels – treat missing boundaries as negative or positive infinity to handle edge cuts uniformly.

What is the Median of Two Sorted Arrays problem?

Given two sorted arrays of sizes m and n, find the median of all m + n elements as if they were merged into one sorted sequence, but do it in O(log min(m, n)) time without actually merging. This is one of the harder binary search problems and a classic interview question.

Why not just merge and find the middle?

Merging both arrays takes O(m + n) time. The optimal approach achieves O(log min(m, n)) by never merging. The idea is a partition: pick a cut in the smaller array, and the matching cut in the larger is forced.

How does the partition idea work?

Let A be the smaller array (size m) and B be the larger (size n). The total elements are m + n. The left half must contain half = (m + n + 1) / 2 elements (using integer division, biased left for odd totals).

Binary-search a cut index i in A from 0 to m. The matching cut in B is j = half - i. The left half consists of A[0..i-1] and B[0..j-1]. The right half is A[i..m-1] and B[j..n-1].

For this to be the correct median split, the crossing condition must hold:
- `maxLeftA <= minRightB`
- `maxLeftB <= minRightA`

A: [1, 3, | 8, 9]     cut i = 2
B: [2, 4, 5, | 6, 7]  cut j = half - i = 3

Left half:  {1, 3, 2, 4, 5}   maxLeft = max(3, 5) = 5
Right half: {8, 9, 6, 7}      minRight = min(8, 6) = 6

Crossing: 3 <= 6? YES.  5 <= 8? YES.  Valid partition!

How do you implement it? (with code)

package com.bank.analysis;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class MedianTwoSortedArrays {

    public static BigDecimal findMedian(BigDecimal[] a, BigDecimal[] b) {
        // Ensure a is the smaller array
        if (a.length > b.length) {
            return findMedian(b, a);
        }

        int m = a.length, n = b.length;
        int half = (m + n + 1) / 2;
        int lo = 0, hi = m;

        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;

            BigDecimal maxLeftA = (i == 0)
                ? new BigDecimal("-999999999") : a[i - 1];
            BigDecimal minRightA = (i == m)
                ? new BigDecimal("999999999") : a[i];
            BigDecimal maxLeftB = (j == 0)
                ? new BigDecimal("-999999999") : b[j - 1];
            BigDecimal minRightB = (j == n)
                ? new BigDecimal("999999999") : b[j];

            if (maxLeftA.compareTo(minRightB) <= 0
                    && maxLeftB.compareTo(minRightA) <= 0) {
                // Valid partition found
                if ((m + n) % 2 == 1) {
                    return maxLeftA.max(maxLeftB);
                } else {
                    BigDecimal maxLeft = maxLeftA.max(maxLeftB);
                    BigDecimal minRight = minRightA.min(minRightB);
                    return maxLeft.add(minRight)
                        .divide(new BigDecimal("2"), 2, RoundingMode.HALF_UP);
                }
            } else if (maxLeftA.compareTo(minRightB) > 0) {
                hi = i - 1;  // took too many from A
            } else {
                lo = i + 1;  // took too few from A
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        BigDecimal[] rajesh = {
            new BigDecimal("100"), new BigDecimal("300"),
            new BigDecimal("800"), new BigDecimal("900")
        };
        BigDecimal[] priya = {
            new BigDecimal("200"), new BigDecimal("400"),
            new BigDecimal("500"), new BigDecimal("600"),
            new BigDecimal("700")
        };
        System.out.println("Median: " + findMedian(rajesh, priya));
    }
}

Median: 500

Why always search the smaller array?

If you searched the larger one, the computed cut in the smaller could go out of its bounds. Swapping so A is always the smaller array guarantees valid cuts and the tightest bound: O(log min(m, n)) instead of O(log max(m, n)).

What are the infinity sentinels?

When a cut lands at the very start (i = 0) or end (i = m) of an array, there is no element on one side. Treat the missing left boundary as negative infinity and the missing right boundary as positive infinity. This lets the crossing comparisons work uniformly without special-casing empty sides.

How do you compute the median from the partition?

| Total count | Median formula |
|---|---|
| Odd | max(maxLeftA, maxLeftB) |
| Even | (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2 |

For even totals with financial amounts, use BigDecimal.divide with a defined RoundingMode so the average is deterministic.

What are the edge cases?

• One array is empty – the median is the middle of the other array.
• Arrays of length one – a single comparison determines the median.
• All elements in one array are smaller – the cut in A is at m and in B is at half - m.
• Duplicate elements – the algorithm works unchanged since duplicates do not affect the crossing condition.

What are common interview follow-up questions?

• Why not merge? – Merging is O(m + n), which is slower than O(log min(m, n)).
• Can you find the K-th element? – Yes, the same partition technique generalizes to finding the K-th smallest.
• What if the arrays are unsorted? – You must sort them first, which dominates the cost at O(n log n).