Median of Two Sorted Arrays: Binary Search on the Partition

Given two sorted arrays a and b (either may be empty, not both), return the median of all their elements together: the middle value if the total count is odd, the mean of the two middle values if it is even. Use O(log(min(m, n))) time.

Examples

Input	Output	Why
`a = [1, 3], b = [2]`	`2.0`
`a = [1, 2], b = [3, 4]`	`2.5`	Merged: 1, 2, 3, 4; (2 + 3) / 2.
`a = [], b = [1]`	`1.0`

Constraints

0 ≤ m, n ≤ 1000, m + n ≥ 1
−10⁶ ≤ values ≤ 10⁶
Return a floating-point number

Hints

Hint 1

The median splits the merged list into a lower half and an upper half. Any such split takes some prefix of a and some prefix of b.

Hint 2

If the lower half has L = ⌈(m + n)/2⌉ elements and takes i of them from a, it takes L − i from b. Only i is free.

Hint 3

The split is right when a[i − 1] ≤ b[L − i] and b[L − i − 1] ≤ a[i]. If a[i − 1] is too big, take fewer from a; if b[L − i − 1] is too big, take more. Binary search i over the shorter array.

Where people lose marks

Searching over the longer array: j can then go negative or past n.
Forgetting the sentinels when i or j is 0 or the full length.
Integer division in the even case: (3 + 4) / 2 must be 3.5, not 3.

Dry run on `[2,7,11,15,22],[1,4,5,9,13,18,20,24]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 4

Step 1 / 4

m5n8L7
13 values, so the lower half holds L = 7. Top: the shorter array a; bottom: b. If the lower half takes i from a, it takes 7 − i from b. Search i in [0, 5].
Step 2 / 4

lo0i2hi5j5
i = 2, j = 5: b[4] = 13 > a[2] = 11. The cut takes too little from a: lo = 3.
Step 3 / 4

lo3i4hi5j3
i = 4, j = 3: a[3] = 15 > b[3] = 9. The cut takes too much from a: hi = 3.
Step 4 / 4

i3j4left max11right min13
i = 3, j = 4: 11 ≤ 13 and 9 ≤ 15, so the cut is right. The total is odd: the median is the largest on the left, 11.

How to think about it

Picture the merged list cut into a lower half of L = ⌈(m + n)/2⌉ elements and an upper half. The lower half consists of a prefix of a of some length i and a prefix of b of length j = L − i. Choosing i fixes everything, and a choice is correct exactly when nothing on the left exceeds anything on the right. Within each array that holds already, so only the two cross conditions remain:

a[i − 1] ≤ b[j] and b[j − 1] ≤ a[i]

(treating a missing element as −∞ on the left or +∞ on the right). If a[i − 1] > b[j], the cut takes too much from a: decrease i. If b[j − 1] > a[i], it takes too little: increase i. The first failure gets worse as i grows and the second gets worse as it shrinks, so binary search over i ∈ [0, m] finds the cut.

At the right cut, the median is the largest element on the left, max(a[i − 1], b[j − 1]), when m + n is odd, and its mean with the smallest on the right, min(a[i], b[j]), when it is even.

Search over the shorter array. Then j = L − i always lies in [0, n], so no index check is needed, and the cost is O(log min(m, n)).

Complexity. Time O(log min(m, n)) · Space O(1)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def median_of_two(a, b):
    if len(a) > len(b):
        a, b = b, a                    # search over the shorter array
    m, n = len(a), len(b)
    half = (m + n + 1) // 2            # size of the lower half
    lo, hi = 0, m
    while True:
        i = (lo + hi) // 2             # take i from a, j from b
        j = half - i
        a_left = a[i - 1] if i > 0 else float('-inf')
        a_right = a[i] if i < m else float('inf')
        b_left = b[j - 1] if j > 0 else float('-inf')
        b_right = b[j] if j < n else float('inf')
        if a_left > b_right:
            hi = i - 1                 # too many from a
        elif b_left > a_right:
            lo = i + 1                 # too few from a
        else:
            low = max(a_left, b_left)
            if (m + n) % 2:
                return float(low)
            return (low + min(a_right, b_right)) / 2

#include <vector>
#include <algorithm>
#include <climits>

double solve(std::vector<int> a, std::vector<int> b) {
    if (a.size() > b.size()) std::swap(a, b);  // search over the shorter array
    const int m = (int)a.size(), n = (int)b.size(), half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    for (;;) {
        int i = lo + (hi - lo) / 2, j = half - i;  // take i from a, j from b
        long long aL = i > 0 ? a[i - 1] : LLONG_MIN, aR = i < m ? a[i] : LLONG_MAX;
        long long bL = j > 0 ? b[j - 1] : LLONG_MIN, bR = j < n ? b[j] : LLONG_MAX;
        if (aL > bR) hi = i - 1;                    // too many from a
        else if (bL > aR) lo = i + 1;               // too few from a
        else {
            long long low = std::max(aL, bL);
            if ((m + n) % 2) return (double)low;
            return (low + std::min(aR, bR)) / 2.0;
        }
    }
}

class Solution {
    public double medianOfTwo(int[] a, int[] b) {
        if (a.length > b.length) { int[] t = a; a = b; b = t; }   // search over the shorter array
        int m = a.length, n = b.length, half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (true) {
            int i = lo + (hi - lo) / 2, j = half - i;          // take i from a, j from b
            long aL = i > 0 ? a[i - 1] : Long.MIN_VALUE, aR = i < m ? a[i] : Long.MAX_VALUE;
            long bL = j > 0 ? b[j - 1] : Long.MIN_VALUE, bR = j < n ? b[j] : Long.MAX_VALUE;
            if (aL > bR) hi = i - 1;                           // too many from a
            else if (bL > aR) lo = i + 1;                      // too few from a
            else {
                long low = Math.max(aL, bL);
                if ((m + n) % 2 == 1) return low;
                return (low + Math.min(aR, bR)) / 2.0;
            }
        }
    }
}

function medianOfTwo(a, b) {
  if (a.length > b.length) [a, b] = [b, a];   // search over the shorter array
  const m = a.length, n = b.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  for (;;) {
    const i = (lo + hi) >> 1, j = half - i;    // take i from a, j from b
    const aL = i > 0 ? a[i - 1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j > 0 ? b[j - 1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL > bR) hi = i - 1;                   // too many from a
    else if (bL > aR) lo = i + 1;              // too few from a
    else {
      const low = Math.max(aL, bL);
      return (m + n) % 2 ? low : (low + Math.min(aR, bR)) / 2;
    }
  }
}

fn solve(a: &[i64], b: &[i64]) -> f64 {
    let (a, b) = if a.len() <= b.len() { (a, b) } else { (b, a) };   // search over the shorter array
    let (m, n) = (a.len(), b.len());
    let half = (m + n + 1) / 2;
    let (mut lo, mut hi) = (0usize, m);
    loop {
        let i = lo + (hi - lo) / 2;            // take i from a, j from b
        let j = half - i;
        let a_l = if i > 0 { a[i - 1] } else { i64::MIN };
        let a_r = if i < m { a[i] } else { i64::MAX };
        let b_l = if j > 0 { b[j - 1] } else { i64::MIN };
        let b_r = if j < n { b[j] } else { i64::MAX };
        if a_l > b_r {
            hi = i - 1;                        // too many from a (i > 0 here)
        } else if b_l > a_r {
            lo = i + 1;                        // too few from a
        } else {
            let low = a_l.max(b_l);
            return if (m + n) % 2 == 1 { low as f64 } else { (low + a_r.min(b_r)) as f64 / 2.0 };
        }
    }
}

import Data.Array

solve :: [Int] -> [Int] -> Double
solve xs ys
  | length xs > length ys = solve ys xs        -- search over the shorter array
  | otherwise = go 0 m
  where
    (m, n) = (length xs, length ys)
    a = listArray (0, m - 1) xs
    b = listArray (0, n - 1) ys
    half = (m + n + 1) `div` 2
    -- Nothing stands for minus or plus infinity at the ends
    go lo hi
      | aL `gt` bR = go lo (i - 1)              -- too many from a
      | bL `gt` aR = go (i + 1) hi              -- too few from a
      | odd (m + n) = fromIntegral low
      | otherwise   = fromIntegral (low + high) / 2
      where
        i = (lo + hi) `div` 2
        j = half - i
        aL = if i > 0 then Just (a ! (i - 1)) else Nothing
        aR = if i < m then Just (a ! i) else Nothing
        bL = if j > 0 then Just (b ! (j - 1)) else Nothing
        bR = if j < n then Just (b ! j) else Nothing
        gt (Just l) (Just r) = l > r            -- a missing element never violates the cut
        gt _ _ = False
        low = maximum [v | Just v <- [aL, bL]]
        high = minimum [v | Just v <- [aR, bR]]

Variants to try

The k-th smallest instead of the median: the elimination search of the previous problem, or this cut search with L = k.
Many sorted arrays: binary search on the value, counting with a lower bound in each array.
A stream of numbers with the median after each one: two heaps, not a binary search.

Next problems

Hard25 min

Median of two sorted arrays

Examples

Constraints

Hints

Where people lose marks

Dry run on `[2,7,11,15,22],[1,4,5,9,13,18,20,24]`

How to think about it

The solution, in six languages

Variants to try

Next problems

The k-th smallest of two sorted arrays

Find a value in a sorted array

Integer square root without a library

Keep going

The k-th smallest of two sorted arrays

Find a value in a sorted array

Integer square root without a library

The pattern behind it

Median of two sorted arrays

Examples

Constraints

Hints

Where people lose marks

Dry run on [2,7,11,15,22],[1,4,5,9,13,18,20,24]

How to think about it

The solution, in six languages

Variants to try

Next problems

The k-th smallest of two sorted arrays

Find a value in a sorted array

Integer square root without a library

Keep going

The k-th smallest of two sorted arrays

Find a value in a sorted array

Integer square root without a library

The pattern behind it

Dry run on `[2,7,11,15,22],[1,4,5,9,13,18,20,24]`