Pattern visualizer
Median of Two Sorted Arrays
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. 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..
Binary search the CUT, not the values
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