Problem 11.9 · Binary SearchHard

Median of Two Sorted Arrays

What it teaches: Binary search a partition of the smaller array so that everything on the left is ≤ everything on the right.

Practise it on judges as “Median of Two Sorted Arrays”.

The problem

Given two sorted arrays a and b, return the median of all their elements combined, in O(log(min(m, n))).

Example 1

Input: a = [1, 3], b = [2]
Output: 2.0

Example 2

Input: a = [1, 2], b = [3, 4]
Output: 2.5

Constraints

0 ≤ m, n ≤ 1000
m + n ≥ 1

Pattern clues in the wording

→ Two sorted arrays, logarithmic time
→ The median splits the combined data into two equal halves

These clues point to Binary Search on an Index: In sorted data, check the middle and throw away the half that can't contain the answer.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        return 0.0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	a = [1,3] b = [2]	2
2	a = [1,2] b = [3,4]	2.5
3	a = [] b = [1]	1

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Merge until the middle · O(m + n)2. Optimal: binary search the partition · O(log(min(m, n)))

Merge until the middle

Time O(m + n) Space O(1)

Walk both arrays with two pointers until reaching the middle position(s).

Approach 1

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int total = a.length + b.length, i = 0, j = 0, prev = 0, cur = 0;
        for (int k = 0; k <= total / 2; k++) {
            prev = cur;
            if (i < a.length && (j >= b.length || a[i] <= b[j])) cur = a[i++];
            else cur = b[j++];
        }
        return total % 2 == 1 ? cur : (prev + cur) / 2.0;
    }
}

Verdict: Simple; misses the logarithmic requirement.

Optimal: binary search the partition

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

Search i in 0..m on the smaller array a; j = half − i. Use −∞/+∞ for elements beyond the ends. If a[i−1] > b[j], move i left; if b[j−1] > a[i], move i right. When balanced, the median comes from the max of the left sides and min of the right sides.

Approach 2

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        if (a.length > b.length) return findMedianSortedArrays(b, a);
        int m = a.length, n = b.length, half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int aLeft = i == 0 ? Integer.MIN_VALUE : a[i - 1];
            int aRight = i == m ? Integer.MAX_VALUE : a[i];
            int bLeft = j == 0 ? Integer.MIN_VALUE : b[j - 1];
            int bRight = j == n ? Integer.MAX_VALUE : b[j];
            if (aLeft > bRight) hi = i - 1;
            else if (bLeft > aRight) lo = i + 1;
            else {
                int leftMax = Math.max(aLeft, bLeft);
                if ((m + n) % 2 == 1) return leftMax;
                return (leftMax + (double) Math.min(aRight, bRight)) / 2.0;
            }
        }
        throw new IllegalArgumentException("arrays not sorted");
    }
}

Verdict: The classic hard binary search.

Before you submit

Edge cases and common mistakes

Test these inputs

One array empty
All of a smaller than all of b
Odd and even totals

Mistakes people make

Searching on the longer array (j can go out of range).
Integer division when averaging the two middle values.

Interview

Follow-up questions

How would you find the kth smallest of two sorted arrays?