The challenge
Return the median of two sorted arrays without merging them.
Both arrays ascending; at least one is nonempty. Values are signed 32-bit integers. Both empty raises an error.
Example
A = [1, 3], B = [2] → 2; A = [1, 2], B = [3, 4] → 2.5.
Use the walkthrough below to inspect the input and each state change.
See Median partition, step by step
Inspect the comparison, the invariant, and the next boundary.
- Left cut bound
- 0
- Cut in A
- —
- Right cut bound
- 1
Search cuts in the shorter array
A has 1 values, B has 2. The combined left side must contain 2 entries.
i ∈ [0, 1]; j = 2 − iRecorded result so far
View exact input
Original A: [1,3] · Original B: [2]
The diagram relabels the shorter array A. Cuts count elements on the left; missing boundary values are −∞ or +∞.
Put it into code
Search a cut in the shorter array. The combined left side must contain ceil((n + m)/2) entries, with all left values ≤ all right values.
Indices are zero-based. C++ uses C++17 or later.
def median_two_sorted(a, b):
# Both arrays sorted; combined input must be nonempty.
if len(a) > len(b):
return median_two_sorted(b, a)
n, m = len(a), len(b)
if n + m == 0:
raise ValueError("Both arrays are empty")
k = (n + m + 1) // 2
left, right = max(0, k - m), min(k, n)
while left <= right:
i = left + (right - left) // 2
j = k - i
al = a[i - 1] if i else float("-inf")
ar = a[i] if i < n else float("inf")
bl = b[j - 1] if j else float("-inf")
br = b[j] if j < m else float("inf")
if al <= br and bl <= ar:
if (n + m) % 2:
return max(al, bl)
return (max(al, bl) + min(ar, br)) / 2
if al > br:
right = i - 1
else:
left = i + 1
raise ValueError("Inputs must be sorted")#include <algorithm>
#include <climits>
#include <stdexcept>
#include <vector>
double median_two_sorted(const std::vector<int>& a, const std::vector<int>& b) {
if (a.size() > b.size()) return median_two_sorted(b, a);
int n = static_cast<int>(a.size()), m = static_cast<int>(b.size());
if (n + m == 0) throw std::invalid_argument("Both arrays are empty");
int k = (n + m + 1) / 2;
int left = std::max(0, k - m), right = std::min(k, n);
while (left <= right) {
int i = left + (right - left) / 2, j = k - i;
long long al = i ? a[i - 1] : LLONG_MIN;
long long ar = i < n ? a[i] : LLONG_MAX;
long long bl = j ? b[j - 1] : LLONG_MIN;
long long br = j < m ? b[j] : LLONG_MAX;
if (al <= br && bl <= ar) {
if ((n + m) % 2) return std::max(al, bl);
return (static_cast<double>(std::max(al, bl)) + std::min(ar, br)) / 2.0;
}
if (al > br) right = i - 1;
else left = i + 1;
}
throw std::invalid_argument("Inputs must be sorted");
}