Median of Two Sorted Arrays: Binary Search Partition

• Partition approach – draw a virtual cut through both arrays so the left combined half and right combined half have equal counts.
• Binary search – search the cut position in the smaller array; derive the cut in the larger array from the half-length formula.
• Balance condition – the partition is correct when left-max of A <= right-min of B and left-max of B <= right-min of A.
• Sentinel values – use negative/positive infinity at array edges to handle empty partitions cleanly.
• Complexity – O(log(min(m, n))) time, O(1) space.

What is the problem?

Given two sorted arrays, find the median of the combined sorted order without merging them. The solution must run in O(log(min(m, n))) time.

At the National Bank of India, the analytics team needs the median transaction amount across two sorted datasets from two different banking systems.

What is the brute-force approach?

Merge both arrays in O(m + n) and read the middle element. This works but does not meet the logarithmic time requirement.

// Brute force: O(m + n)
int[] merged = mergeSorted(a, b);
int total = merged.length;
if (total % 2 == 1) return merged[total / 2];
else return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;

How does the binary search partition work?

Always search the shorter array (call it A of length m). Pick a cut position i in A, then the cut in B is j = (m + n + 1) / 2 - i. This ensures the left side has exactly half the total elements.

package com.bank.analytics;

public class MedianTwoSortedArrays {
    public static double findMedian(int[] a, int[] b) {
        if (a.length > b.length) return findMedian(b, a);

        int m = a.length, n = b.length;
        int low = 0, high = m;

        while (low <= high) {
            int i = (low + high) / 2;
            int j = (m + n + 1) / 2 - i;

            int aLeftMax  = (i == 0) ? Integer.MIN_VALUE : a[i - 1];
            int aRightMin = (i == m) ? Integer.MAX_VALUE : a[i];
            int bLeftMax  = (j == 0) ? Integer.MIN_VALUE : b[j - 1];
            int bRightMin = (j == n) ? Integer.MAX_VALUE : b[j];

            if (aLeftMax <= bRightMin && bLeftMax <= aRightMin) {
                if ((m + n) % 2 == 1) {
                    return Math.max(aLeftMax, bLeftMax);
                } else {
                    return (Math.max(aLeftMax, bLeftMax)
                          + Math.min(aRightMin, bRightMin)) / 2.0;
                }
            } else if (aLeftMax > bRightMin) {
                high = i - 1;
            } else {
                low = i + 1;
            }
        }
        throw new IllegalArgumentException("Input arrays are not sorted");
    }

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

Median: 450.0

Why always search the shorter array?

Searching the shorter array bounds the binary search range to O(log(min(m, n))). It also guarantees that the derived cut j stays within bounds of the longer array. If you searched the longer array, j could go negative.

How do the sentinel values work?

When i = 0, the left side of A is empty, so aLeftMax should be negative infinity (will never violate the condition). When i = m, the right side of A is empty, so aRightMin should be positive infinity. This eliminates special-case branches.

int aLeftMax  = (i == 0) ? Integer.MIN_VALUE : a[i - 1];
int aRightMin = (i == m) ? Integer.MAX_VALUE : a[i];

What is the partition balance condition?

The partition is correct when:
- `aLeftMax <= bRightMin` (everything on A's left is <= everything on B's right)
- `bLeftMax <= aRightMin` (everything on B's left is <= everything on A's right)

If aLeftMax > bRightMin, the cut in A is too far right, so move high = i - 1.
If bLeftMax > aRightMin, the cut in A is too far left, so move low = i + 1.

How do you read the median from the partition?

• Once balanced:
• Odd total: median = max(aLeftMax, bLeftMax). The larger of the two left-edge values is the middle element.
• Even total: median = average of max(aLeftMax, bLeftMax) and min(aRightMin, bRightMin).

What is the time and space complexity?

| Approach | Time | Space |
|---|---|---|
| Binary search partition | O(log(min(m, n))) | O(1) |
| Merge and find middle | O(m + n) | O(m + n) |

What are common mistakes?

Searching the longer array, which can cause j to go negative.

// Wrong: if a is longer and i is large, j = (m+n+1)/2 - i can be negative
int j = (m + n + 1) / 2 - i; // j < 0 -> ArrayIndexOutOfBoundsException

// Correct: always make a the shorter array
if (a.length > b.length) return findMedian(b, a);

What are the edge cases?

• One array is empty: the median is the middle of the other array.
• Both arrays have one element: median is their average (even total) or the smaller (odd total with duplication).
• All elements of A are smaller than all of B: the partition puts all of A on the left.
• Arrays of very different lengths: the binary search still works because we search the shorter one.

What should a senior engineer know?

This is one of the hardest binary search problems and a classic LeetCode hard. The key insight is that finding the median is equivalent to finding the correct partition. The partition approach generalizes to finding the kth element in two sorted arrays.

For BigDecimal amounts, use compareTo for comparisons and add().divide(TWO) for the average.

What are common interview follow-up questions?

• How would you find the kth smallest element instead of the median? (Adjust the half-length formula.)
• What if there are more than two sorted arrays? (Use a min-heap to merge k arrays.)
• What if the arrays are not sorted? (Sort first, which costs O(n log n), or use QuickSelect on the merged view.)