How Do You Find the Median of Two Sorted Arrays?
Learn the O(log(min(m, n))) binary search approach to find the median of two sorted arrays for your next interview.
Expected Interview Answer
The median of two sorted arrays can be found in O(log(min(m, n))) time by binary searching a partition point on the smaller array, choosing a matching partition on the larger array so that every element on the left side is less than or equal to every element on the right side.
The trick is to avoid merging the arrays at all: instead, pick a partition index on the smaller array, derive the matching partition on the larger array from the fact that the combined left half must have exactly half the total elements, and check whether the four boundary elements satisfy the sorted-partition condition. If the left side's max exceeds the right side's min, the binary search moves the partition left or right accordingly. Once a valid partition is found, the median is either the max of the left side (odd total) or the average of the max-left and min-right (even total). Binary searching over the smaller array's length bounds the search space to O(log(min(m, n))), which beats the O(m+n) merge approach required by a brute-force solution.
- O(log(min(m, n))) time, better than O(m + n) merging
- No extra array construction needed
- Handles empty arrays and uneven sizes correctly
- Generalizes to finding the k-th smallest across two arrays
AI Mentor Explanation
Imagine two sorted stacks of scorecards from two different tournaments, and you need the middle score across both combined without physically merging the stacks. You guess a cut point in the smaller stack, then compute exactly where the cut must fall in the larger stack so the two cuts together leave exactly half the total cards on the left. You check the four cards at the cut edges; if the left side's highest score beats the right side's lowest, you slide the cut in the smaller stack left, otherwise right. This binary search over just the smaller stack finds the correct cut in far fewer comparisons than shuffling both stacks together.
Step-by-Step Explanation
Step 1
Ensure the smaller array is searched
Swap arrays if needed so the binary search runs over the shorter one, bounding time to O(log(min(m, n))).
Step 2
Binary search a partition point
Pick a cut index on the smaller array; derive the matching cut on the larger array from the required left-half size.
Step 3
Check the boundary condition
Valid if max of both left sides <= min of both right sides; otherwise move the smaller array's cut left or right.
Step 4
Compute the median
Odd total: max of the left side. Even total: average of max-left and min-right.
What Interviewer Expects
- Justify why binary searching the smaller array bounds the complexity
- Correctly derive the matching partition index on the larger array
- Handle edge cases: empty array, partition at index 0 or length
- State and prove the O(log(min(m, n))) complexity
Common Mistakes
- Merging both arrays first, giving O(m + n) instead of the expected O(log(min(m, n)))
- Forgetting to handle partitions that land at the array boundary (use -infinity/+infinity sentinels)
- Binary searching the larger array instead of the smaller one
- Getting the even-vs-odd total median formula backwards
Best Answer (HR Friendly)
“I find the median without actually merging the two arrays. I binary search for a split point on the smaller array and calculate the matching split on the larger one so both sides are correctly balanced, which finds the answer in logarithmic time instead of linear time.”
Code Example
def find_median_sorted_arrays(a, b):
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi = 0, m
half = (m + n + 1) // 2
while lo <= hi:
i = (lo + hi) // 2
j = half - i
a_left = a[i - 1] if i > 0 else float("-inf")
a_right = a[i] if i < m else float("inf")
b_left = b[j - 1] if j > 0 else float("-inf")
b_right = b[j] if j < n else float("inf")
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2 == 1:
return max(a_left, b_left)
return (max(a_left, b_left) + min(a_right, b_right)) / 2
elif a_left > b_right:
hi = i - 1
else:
lo = i + 1
raise ValueError("Input arrays are not sorted")Follow-up Questions
- How would you generalize this to find the k-th smallest element across two sorted arrays?
- What happens if one of the arrays is empty?
- Why does binary searching the smaller array matter for the time complexity?
- How would you extend this approach to more than two sorted arrays?
MCQ Practice
1. What is the time complexity of the optimal median-of-two-sorted-arrays solution?
Binary searching a partition over only the smaller array bounds the search to O(log(min(m, n))).
2. What condition confirms a valid partition between the two arrays?
A valid partition requires every left-side element to be <= every right-side element across both arrays.
3. For an even total number of elements, how is the median computed once a valid partition is found?
With an even combined length, the median is the average of the largest left-side value and smallest right-side value.
Flash Cards
Why binary search the smaller array? — It bounds the time complexity to O(log(min(m, n))) instead of searching the larger one.
What defines a valid partition between two sorted arrays? — max(leftA, leftB) <= min(rightA, rightB).
How is the median computed for an odd total length? — It is the maximum value among the two left-side boundary elements.
What sentinels handle partitions at an array's edge? — Negative infinity for an empty left side, positive infinity for an empty right side.