Back to solutions

Median of Two Sorted Arrays

HardBinary Search

Return the median of two sorted arrays in O(log(min(m, n))) time.

Open problem
Constraints
  • 0 <= m, n <= 1000
  • 1 <= m + n

Binary search on the partition

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

Binary search a cut in the smaller array so that the left parts of both arrays form the lower half. Adjust the cut until the largest left element is at most the smallest right element, then read off the median.

#include <bits/stdc++.h>
using namespace std;

double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
    if (a.size() > b.size()) return findMedianSortedArrays(b, a);
    int m = a.size(), n = b.size();
    int lo = 0, hi = m, half = (m + n + 1) / 2;
    while (lo <= hi) {
        int i = (lo + hi) / 2, j = half - i;
        int aLeft = i == 0 ? INT_MIN : a[i-1];
        int aRight = i == m ? INT_MAX : a[i];
        int bLeft = j == 0 ? INT_MIN : b[j-1];
        int bRight = j == n ? INT_MAX : b[j];
        if (aLeft <= bRight && bLeft <= aRight) {
            if ((m + n) % 2) return max(aLeft, bLeft);
            return (max(aLeft, bLeft) + min(aRight, bRight)) / 2.0;
        } else if (aLeft > bRight) hi = i - 1;
        else lo = i + 1;
    }
    return 0.0;
}