visual walkthrough
Median of Two Sorted Arrays
The famous O(log(min(m,n))) partition problem.
The idea
The median splits all the numbers into a smaller half and a bigger half. Choosing how many come from the first array fixes how many come from the second.
Binary search that one number: if the left side has something too big from one array, take fewer from it.
Complexity
| approach | time | space |
|---|---|---|
| Merge up to the middle | O(m + n) | O(m + n) |
| Binary search the cut | O(log min(m, n)) | O(1) |