Median of Two Sorted Arrays

Problem Statement

Given two sorted arrays a and b, return the median of the combined set. The target complexity is O(log(m+n)).

Example

Input:  a = [1,3], b = [2]
Output: 2.0
Explanation: merged = [1,2,3], median 2.

Approach

Binary search a partition of the smaller array. Choose i elements from a and j = (m+n+1)/2 - i from b for the left half. The partition is correct when aLeft <= bRight and bLeft <= aRight. Use ±∞ sentinels for the edges.

Complexity

• Time: O(log(min(m, n)))
• Space: O(1)

Solution Code

Python

def findMedianSortedArrays(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
        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:
            if (m + n) % 2:
                return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        elif aL > bR:
            hi = i - 1
        else:
            lo = i + 1
    return 0.0

Java

double findMedianSortedArrays(int[] a, int[] b) {
    if (a.length > b.length) { int[] t = a; a = b; b = t; }
    int m = a.length, n = b.length, lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) / 2, j = (m + n + 1) / 2 - i;
        double aL = i > 0 ? a[i-1] : Double.NEGATIVE_INFINITY;
        double aR = i < m ? a[i]   : Double.POSITIVE_INFINITY;
        double bL = j > 0 ? b[j-1] : Double.NEGATIVE_INFINITY;
        double bR = j < n ? b[j]   : Double.POSITIVE_INFINITY;
        if (aL <= bR && bL <= aR) {
            if (((m + n) & 1) == 1) return Math.max(aL, bL);
            return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
        } else if (aL > bR) hi = i - 1;
        else lo = i + 1;
    }
    return 0.0;
}

C++

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    if (a.size() > b.size()) swap(a, b);
    int m = a.size(), n = b.size(), lo = 0, hi = m;
    while (lo <= hi) {
        int i = (lo + hi) / 2, j = (m + n + 1) / 2 - i;
        double aL = i > 0 ? a[i-1] : -1e18;
        double aR = i < m ? a[i]   :  1e18;
        double bL = j > 0 ? b[j-1] : -1e18;
        double bR = j < n ? b[j]   :  1e18;
        if (aL <= bR && bL <= aR) {
            if ((m + n) & 1) return max(aL, bL);
            return (max(aL, bL) + min(aR, bR)) / 2.0;
        } else if (aL > bR) hi = i - 1;
        else lo = i + 1;
    }
    return 0.0;
}

Key Takeaways

• Always binary-search the smaller array to keep it O(log(min(m,n))).
• Sentinels (±∞) remove special-casing at the array edges.
• Reference: LeetCode 4 (Median of Two Sorted Arrays).