Median of Two Sorted Arrays

Hard#4search the cut

You get two sorted arrays. Find the median of all their numbers together — the middle one, or the mean of the two middle ones for an even count — in O(log(m + n)) time. Our example: a = [1, 5, 9, 12, 20], b = [2, 3, 7, 10, 15, 18] — 11 numbers, the answer is 9.

4 Median of Two Sorted ArraysWalkthrough · 1×

Example: a = [1, 5, 9, 12, 20], b = [2, 3, 7, 10, 15, 18]. The lines are the cuts: i numbers of a and j of b go to the left half. lo and hi bound the cut in a.

a011529312420b021327310415518
goes to the left halfgoes to the right halfcompared at the cutsthe median

a is the shorter array, 5 numbers. Its cut can take 0..5 of them: lo = 0

01/23
restart · back · play · step
Speed
1function findMedian(a, b): // a is the shorter one
2 lo = 0
3 hi = len(a)
4 half = floor((len(a) + len(b) + 1) / 2)
5 while lo <= hi:
6 i = floor((lo + hi) / 2) // how many of a go left
7 j = half - i // the rest of the left half, from b
8 if a[i - 1] > b[j]: // past an end: −∞ or +∞
9 hi = i - 1 // too many from a
10 else if b[j - 1] > a[i]:
11 lo = i + 1 // too few from a
12 else: // every left number <= every right one
13 leftMax = max(a[i - 1], b[j - 1])
14 if (len(a) + len(b)) is odd:
15 return leftMax
16 return (leftMax + min(a[i], b[j])) / 2
state
lo
0
hi
–
half
–
i
–
j
–
leftMax
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The median splits all the numbers into two halves where every left number is at most every right one. If i numbers come from a, the other half − i must come from b, so the cut in a alone decides the split.
  2. Each array is sorted, so only two pairs can be out of order: a[i − 1] with b[j] and b[j − 1] with a[i]. If a[i − 1] > b[j], too many come from a and the cut moves left; if b[j − 1] > a[i], too few, and it moves right. That is a binary search over i.
  3. Searching over the shorter array keeps j between 0 and len(b). Here it takes three cuts: 2 is too few, 4 too many, 3 is right.

Complexity

Time O(log(min(m, n))): binary search over the cut in the shorter array. Memory O(1): the arrays are never merged.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.