Approach Summary
Binary search on the partition of the shorter array such that the left half of both arrays combined equals the right half.
How to Recognize This Pattern
- Merge-and-find would be O(m+n) — hard wants O(log)
- Think about partition indices, not merge
Complexity Analysis
Time Complexity
O(log(min(m, n)))
Space Complexity
O(1)
Tags
Array Binary Search Divide and Conquer