Median of Two Sorted Arrays
Find the median of two sorted arrays without merging them, by binary searching for the right place to cut the shorter array, in O(log(min(m, n))).
Updated Medium read: 8 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Merge, then take the middle | O(m + n) | O(m + n) |
| Binary search on the cut | O(log(min(m, n))) | O(1) |
The problem
You are given two arrays, each sorted in ascending order. Return the median of all their values taken together. The solution must run in O(log(m + n)) time, where m and n are the two lengths. At least one of the arrays is not empty.
The median is the middle value of a sorted list. With an odd number of values it is the one in the centre. With an even number it is the average of the two in the centre.
first = [1, 3], second = [2] → 2 (combined: 1, 2, 3)
first = [1, 2], second = [3, 4] → 2.5 (combined: 1, 2, 3, 4; average of 2 and 3)
first = [], second = [1] → 1Approach 1: merge, then take the middle
Both arrays are sorted, so they can be merged into one sorted array by repeatedly taking the smaller of the two front values. The median is then read straight from the middle.
JavaScript
function findMedianByMerging(first, second) {
const merged = [];
let i = 0;
let j = 0;
while (i < first.length || j < second.length) {
const takeFirst =
j >= second.length || (i < first.length && first[i] <= second[j]);
merged.push(takeFirst ? first[i++] : second[j++]);
}
const mid = Math.floor(merged.length / 2);
if (merged.length % 2 === 1) return merged[mid];
return (merged[mid - 1] + merged[mid]) / 2;
}Python
def find_median_by_merging(first, second):
merged = []
i = 0
j = 0
while i < len(first) or j < len(second):
take_first = j >= len(second) or (
i < len(first) and first[i] <= second[j]
)
if take_first:
merged.append(first[i])
i += 1
else:
merged.append(second[j])
j += 1
mid = len(merged) // 2
if len(merged) % 2 == 1:
return merged[mid]
return (merged[mid - 1] + merged[mid]) / 2Time O(m + n), space O(m + n). This is a perfectly good answer in practice, but it is linear, and the problem asks for logarithmic time. A logarithmic bound is a strong hint that the answer involves binary search and must not look at every element.
Restating the question as a cut
The median splits the combined values into a left half and a right half of equal size (the left half gets the extra one when the total is odd), with everything on the left no larger than everything on the right.
That split can be described without merging anything. Cut each array into a left part and a right part:
first: 1 3 | 8 9 15
second: 7 11 18 19 | 21 25If the two left parts together hold exactly half of all the values, and nothing on the left is larger than anything on the right, then the left parts are the left half of the merged array, whatever order they would be merged in. The median sits at the boundary.
Two things make this searchable:
- Only one cut is free. The left side must hold
halfvalues in total, so choosing how many to take fromfirstfixes how many come fromsecond:cutSecond = half − cutFirst. - Only two comparisons are needed. Within each array the left part is already no larger than the right part. The split is correct when the same holds across the arrays: the last value on the left of
firstis no larger than the first value on the right ofsecond, and the other way round.
Approach 2: binary search on the cut
Name the four values next to the cuts:
| Name | Meaning |
|---|---|
leftFirst |
Last value in the left part of first |
rightFirst |
First value in the right part of first |
leftSecond |
Last value in the left part of second |
rightSecond |
First value in the right part of second |
Then for any choice of cutFirst there are three cases:
| Condition | What it means | Action |
|---|---|---|
leftFirst > rightSecond |
Too many values taken from first |
Move the cut left |
leftSecond > rightFirst |
Too few values taken from first |
Move the cut right |
| Neither | The split is correct | Read off the median |
Moving the cut in first to the left makes leftFirst smaller and, because the cut in second moves right to compensate, makes rightSecond larger. So the first condition flips from true to false exactly once as the cut moves, and that single switching point is what binary search finds.
When a cut is at the very start or end of an array, one of the four values does not exist. Using -Infinity for a missing left value and Infinity for a missing right value makes the comparisons come out correctly with no special cases.
JavaScript
function findMedianSortedArrays(first, second) {
if (first.length > second.length) {
return findMedianSortedArrays(second, first);
}
const total = first.length + second.length;
const half = Math.floor((total + 1) / 2);
let lo = 0;
let hi = first.length;
while (lo <= hi) {
const cutFirst = lo + Math.floor((hi - lo) / 2);
const cutSecond = half - cutFirst;
const leftFirst = cutFirst > 0 ? first[cutFirst - 1] : -Infinity;
const rightFirst = cutFirst < first.length ? first[cutFirst] : Infinity;
const leftSecond = cutSecond > 0 ? second[cutSecond - 1] : -Infinity;
const rightSecond = cutSecond < second.length ? second[cutSecond] : Infinity;
if (leftFirst > rightSecond) {
hi = cutFirst - 1;
} else if (leftSecond > rightFirst) {
lo = cutFirst + 1;
} else {
const leftMax = Math.max(leftFirst, leftSecond);
if (total % 2 === 1) return leftMax;
return (leftMax + Math.min(rightFirst, rightSecond)) / 2;
}
}
}Python
def find_median_sorted_arrays(first, second):
if len(first) > len(second):
return find_median_sorted_arrays(second, first)
total = len(first) + len(second)
half = (total + 1) // 2
lo = 0
hi = len(first)
low, high = float("-inf"), float("inf")
while lo <= hi:
cut_first = lo + (hi - lo) // 2
cut_second = half - cut_first
left_first = first[cut_first - 1] if cut_first > 0 else low
right_first = first[cut_first] if cut_first < len(first) else high
left_second = second[cut_second - 1] if cut_second > 0 else low
right_second = second[cut_second] if cut_second < len(second) else high
if left_first > right_second:
hi = cut_first - 1
elif left_second > right_first:
lo = cut_first + 1
else:
left_max = max(left_first, left_second)
if total % 2 == 1:
return left_max
return (left_max + min(right_first, right_second)) / 2Once the split is correct, the largest value on the left is leftMax and the smallest on the right is the lower of the two right values. With an odd total the left half has the extra value, so leftMax is the median. With an even total the median is the average of the two values either side of the boundary.
Walkthrough
first = [1, 3, 8, 9, 15], second = [7, 11, 18, 19, 21, 25]. There are 11 values, so half is 6.
| lo | hi | cutFirst | cutSecond | leftFirst | rightFirst | leftSecond | rightSecond | Result |
|---|---|---|---|---|---|---|---|---|
| 0 | 5 | 2 | 4 | 3 | 8 | 19 | 21 | 19 > 8: too few from first, lo = 3 |
| 3 | 5 | 4 | 2 | 9 | 15 | 11 | 18 | 9 ≤ 18 and 11 ≤ 15: correct |
The left parts are [1, 3, 8, 9] and [7, 11]. The total is odd, so the median is the largest value on the left: max(9, 11) = 11. Merging by hand gives 1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25, whose sixth value is indeed 11. The search looked at two cuts and never touched most of the values.
Time O(log(min(m, n))): the search runs over the shorter array only. Space O(1).
Why search the shorter array
Swapping the arrays at the top so that first is the shorter one does two jobs.
- It keeps
cutSecondin range.cutSecondishalf − cutFirst. Iffirstwere the longer array, taking many values from it could makecutSecondnegative, and taking few could push it past the end ofsecond. Withfirstthe shorter,cutSecondalways lands between 0 andsecond.length. - It is faster. The number of steps depends on the length of the array being searched, so the shorter one is the cheaper choice.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(findMedianSortedArrays([1, 3], [2])); // 2
console.log(findMedianSortedArrays([1, 2], [3, 4])); // 2.5Python
print(find_median_sorted_arrays([1, 3], [2])) # 2
print(find_median_sorted_arrays([1, 2], [3, 4])) # 2.5The comment after each line is the result you should see.
Common mistakes
- Searching the longer array.
cutSecondgoes out of range and the code reads values that are not there. - Setting
hitofirst.length - 1. There arefirst.length + 1places to cut, including taking every element, sohistarts atfirst.length. - Handling empty parts with special cases. Separate branches for "cut at the start" and "cut at the end" multiply quickly. The two infinities cover all of them.
- Using
Math.floor(total / 2)forhalf. It can be made to work, but then the odd case reads the median from the right side instead. Pick one convention and keep the median calculation consistent with it. - Forgetting the even case. With an even total the answer is an average and may not be a whole number.
Original problem: LeetCode 4: Median of Two Sorted Arrays