For the best experience, we recommend using a widescreen desktop

Divide & Conquer

Median of Two Sorted Arrays

Finds the median of two sorted arrays in O(log n) via binary search.

Step 1 of 3

Find the median of two sorted arrays of lengths 5 and 6. Binary search on the shorter array to find the correct partition.

▶Algorithm
Median(A, B):
ensure len(A) ≤ len(B)
lo = 0; hi = len(A)
while lo ≤ hi:
i = (lo+hi)/2; j = (m+n+1)/2 − i
if valid partition: compute median
if A[i−1] > B[j]: hi = i−1
else: lo = i+1

How It Works

Binary search on the shorter array to find partition i. Then j = (m+n+1)/2 − i. A valid partition satisfies A[i−1] ≤ B[j] and B[j−1] ≤ A[i]. O(log(min(m,n))) time.

Array A
←left
1
0
3
1
8
2
9
3
15
4
right→
Array B
←left
7
0
11
1
18
2
19
3
21
4
25
5
right→
Binary search on A: lo = 0, hi = 5
Partition boundary
Left half
1 / 3Speed