Median of Two Sorted Arrays
Binary search the CUT, not the values
The median is the point where the combined values split into a smaller half and a larger half of equal size, and finding it needs only the position of that split, not the merged array. Cutting A after i values forces B to be cut after half - i, so a single number i decides both cuts, and a pair of cuts is correct exactly when nothing on the left exceeds anything on the right. That test is monotonic in i — too small an i fails one way, too large fails the other — so binary search lands on it in O(log min(m,n)) probes. A cut past either end counts as -inf on the left or +inf on the right, so those checks pass automatically. This trace uses 7 values, an odd count, so the median is the largest value on the left; an even count averages it with the smallest value on the right.
Details
Animated on: A = [1,3,8], B = [7,9,10,11] — both sorted. Find the median of the combined 7 values in O(log min(m,n)), without merging them.
Problem:Median of Two Sorted ArraysHard
Binary search the CUT, not the values
step 1 / 9
A=[1,3,8] and B=[7,9,10,11] are each already sorted, 7 values in total. Merging them outright costs O(3+4) work to produce values nobody reads; instead cut each array once so the 4 smallest values all land left of the cuts, because the median is decided entirely by the values touching those cuts.
1FUNCTION median(A, B)2 low <- 03 high <- LENGTH(A)4 WHILE low <= high5 i <- (low + high) / 26 j <- (LENGTH(A) + LENGTH(B) + 1) / 2 - i7 IF A[i - 1] > B[j]8 high <- i - 19 ELSE IF B[j - 1] > A[i]10 low <- i + 111 ELSE12 RETURN MAX(A[i - 1], B[j - 1])
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- A=[1,3,8] and B=[7,9,10,11] are each already sorted, 7 values in total. Merging them outright costs O(3+4) work to produce values nobody reads; instead cut each array once so the 4 smallest values all land left of the cuts, because the median is decided entirely by the values touching those cuts.
- Only A's cut has to be searched: if A hands i values to the left half, B is forced to hand over the remaining 4-i, so one number i fixes both cuts. That leaves the range low=0..high=3 to binary search, and picking A as the shorter array is what keeps the range that short.
- Try i=1: A contributes its first 1 value, so B must contribute j=4-1=3 to fill the left half, which becomes [1,7,9,10]. Only the values touching the cuts decide whether that split is legal: A[0]=1 and B[2]=10 on the left, A[1]=3 and B[3]=11 on the right.
- B[2]=10 is on the left yet outranks A[1]=3 on the right, so the split is illegal. B is being asked for too many values, which is the same as A giving too few, so every smaller i fails too: low = 1+1 = 2.
- Try i=2: A contributes its first 2 values, so B must contribute j=4-2=2 to fill the left half, which becomes [1,3,7,9]. Only the values touching the cuts decide whether that split is legal: A[1]=3 and B[1]=9 on the left, A[2]=8 and B[2]=10 on the right.
- B[1]=9 is on the left yet outranks A[2]=8 on the right, so the split is illegal. B is being asked for too many values, which is the same as A giving too few, so every smaller i fails too: low = 2+1 = 3.
- Try i=3: A contributes its first 3 values, so B must contribute j=4-3=1 to fill the left half, which becomes [1,3,7,8]. Only the values touching the cuts decide whether that split is legal: A[2]=8 and B[0]=7 on the left, +inf (A is used up) and B[1]=9 on the right.
- Both cross-checks hold: A[2]=8 <= B[1]=9 and B[0]=7 <= +inf (A is used up). Nothing on the left exceeds anything on the right, so these 4 values are exactly the 4 smallest of all 7 — established in a handful of probes, with the arrays never merged.
- 7 values is an odd count, so the median is just the largest value left of the cuts: 8. Had the count been even, the median would average it with the smallest value on the right instead.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.