Median of Two Sorted Arrays
Find the median of two sorted arrays in logarithmic time.
Pattern fit
The hard part is not the median itself but finding a partition where the left half contains exactly the right number of elements and every left element is <= every right element.
Key observation
Binary search on the partition index of the shorter array because the partition in the longer array is then determined automatically.
Target complexity
O(log(min(m,n))) / O(1)
How to break down the solution cleanly
The hard part is not the median itself but finding a partition where the left half contains exactly the right number of elements and every left element is <= every right element.
Binary search on the partition index of the shorter array because the partition in the longer array is then determined automatically.
Write the monotonic predicate in plain English first.
Choose a search interval that definitely contains the answer.
Reference implementation
Python# Generic pattern template
# Find first position where check(mid) is true
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
Common pitfalls
Binary-searching the longer array and making boundary handling harder.
Not using sentinel values when one side of a partition is empty.
Common follow-ups
Could you explain the same idea without code using partition language?
Why does searching the shorter array simplify correctness?
Continue with related problems
Build repeatable depth inside the Binary Search cluster before moving on.