A pricing fairness job is given two already sorted catalogs — domestic SKUs and imported SKUs — and must report the median list price of the combined set. The first version merged both arrays, then picked the middle slot (or the average of the two middles). A few hundred SKUs per list returned instantly. After the marketplace ingest, tens of millions of rows were still merging when the nightly report timed out.
Median of Two Sorted Arrays asks for a cut, not a merged list. An array already gives a[i] for free. A merge uses that and still pays O(m + n). Both inputs are sorted, so you can binary-search how many elements the left half takes from the shorter array. You never build the combined list.
This is an interview writeup, not a procedure lecture. The binary search post owns the invariant and mid overflow. The membership writeup discards the half that cannot hold a key. Here there is no key. We only search a partition index.
The problem
Given two sorted int[] arrays a and b of lengths m and n (either may be empty, not both), return the median of the combined sorted sequence as a double. If m + n is odd, that is the middle value. If even, it is the average of the two central values. Typical interviews want O(log(m + n)) time.
a = [2, 7, 11], b = [4, 9, 13, 18] → 9.0
a = [3, 8], b = [5, 12, 20, 25] → 10.0
a = [], b = [6] → 6.0First row combined is [2, 4, 7, 9, 11, 13, 18]; the middle is 9. Second row combined is [3, 5, 8, 12, 20, 25]; the two middles are 8 and 12, average 10.0.
Note: Do not sort a concatenation. Both arrays are already ordered. The bill you are avoiding is the merge, not a sort.
Merge then pick is the honest brute force
Two-pointer merge into a new array, then read the middle (or the average of two middles). Correct. Linear in m + n, extra linear space.
double medianMerge(int[] a, int[] b) {
int[] merged = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
merged[k++] = a[i] <= b[j] ? a[i++] : b[j++];
}
while (i < a.length) {
merged[k++] = a[i++];
}
while (j < b.length) {
merged[k++] = b[j++];
}
int t = merged.length;
if (t % 2 == 1) {
return merged[t / 2];
}
return (merged[t / 2 - 1] + merged[t / 2]) / 2.0;
}You can stop the merge at the middle and keep only two running values. Still linear. At catalog scale you paid a full walk for a question a cut answers in a handful of probes: is this partition a valid median cut?
Binary search the cut on the shorter array
Swap so a is the shorter. You will choose i — how many of a’s elements sit on the left of the cut — with a binary search in 0 .. m. The left half of the combined sequence must hold half = (m + n + 1) / 2 elements, so the left of b takes j = half - i. The + 1 puts the extra element on the left when the total is odd, so the median is always a left-side max (or the average of that max and the right-side min when even).
A cut is legal when both sides respect order across the seam:
maxLeftA <= minRightBmaxLeftB <= minRightA
If i == 0 there is no left a; treat maxLeftA as -∞. If i == m there is no right a; treat minRightA as +∞. Same for b at j == 0 and j == n.
- If
maxLeftA > minRightB,iis too far right:hi = i - 1. - If
maxLeftB > minRightA,iis too far left:lo = i + 1. - Otherwise the cut is the median. Odd total:
max(maxLeftA, maxLeftB). Even: average that withmin(minRightA, minRightB).
Search the shorter array. i ranges 0 .. m. Searching the longer one lets j = half - i fall outside 0 .. n. On the shorter, j stays in range for every i.
Walk a = [2, 7, 11] and b = [4, 9, 13, 18]. m = 3, n = 4, half = 4. Combined left needs four values.
i in [0, 3] on a = [2, 7, 11]
i=1 j=3
left a:[2] b:[4, 9, 13]
right a:[7, 11] b:[18]
maxLeftA=2 minRightA=7
maxLeftB=13 minRightB=18
13 > 7 → i too small, lo=2
i=2 j=2
left a:[2, 7] b:[4, 9]
right a:[11] b:[13, 18]
maxLeftA=7 minRightA=11
maxLeftB=9 minRightB=13
7<=13 and 9<=11 → cut
odd → max(7, 9) = 9The even row [3, 8] and [5, 12, 20, 25] lands on i = 2, j = 1: left {3, 8, 5}, right {12, 20, 25}. maxLeft = 8, minRight = 12, average 10.0.
The Java is that search. Bounds are long so a real Integer.MIN_VALUE in the input is not confused with a sentinel.
double findMedianSortedArrays(int[] a, int[] b) {
if (a.length > b.length) {
int[] tmp = a;
a = b;
b = tmp;
}
int m = a.length;
int n = b.length;
int lo = 0;
int hi = m;
int half = (m + n + 1) / 2;
while (lo <= hi) {
int i = lo + (hi - lo) / 2;
int j = half - i;
long maxLeftA = (i == 0) ? Long.MIN_VALUE : a[i - 1];
long minRightA = (i == m) ? Long.MAX_VALUE : a[i];
long maxLeftB = (j == 0) ? Long.MIN_VALUE : b[j - 1];
long minRightB = (j == n) ? Long.MAX_VALUE : b[j];
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
if (((m + n) & 1) == 1) {
return Math.max(maxLeftA, maxLeftB);
}
return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2.0;
}
if (maxLeftA > minRightB) {
hi = i - 1;
} else {
lo = i + 1;
}
}
throw new IllegalArgumentException("both empty");
}Time is O(log(min(m, n))) — the search runs on the shorter length; that is O(log(m + n)) as asked. Space is O(1) — a handful of indices, no merged buffer. Mid overflow already lives on the algorithms post; do not re-lecture it unless they ask.
Note: Drop i on a miss: lo = i + 1 / hi = i - 1. i is a count of elements, not a peak candidate — the opposite of the slope-search hi = mid contract. Compare with <= across the seam; duplicates are legal.
What interviewers usually poke next
- k-th element of two sorted arrays. Same cut, different
half. The median is that problem atk = (m + n + 1) / 2(and the next slot when even). - One array empty.
m = 0,istays0,j = half, and the median is taken entirely fromb. Name it; the same loop handles it. - Why not search the longer.
jcan leave[0, n]. Swap first, then the shorter range is the whole story. - Both empty / null. The prompt promised at least one value. In production you would reject; at the board, ask.
You are done with this problem when you can say, out loud, why the merge is correct, why the left size is (m + n + 1) / 2, why both maxLeft <= minRight checks are required, and why the binary search runs on the shorter array.