Modified Binary Search
LC #4Hard
Median of Two Sorted Arrays
Modified Binary Search
AmazonGoogleMetaBloombergAppleProblem
Find the median of two sorted arrays in O(log(m+n)) time.
arraybinary-searchdivide-and-conquer
Constraints
- ›0 ≤ m, n ≤ 1000
- ›-10⁶ ≤ nums1[i], nums2[j] ≤ 10⁶
- ›O(log(m+n)) runtime required
Example
Input
nums1 = [1, 3], nums2 = [2]Output
2.0Why
Merged: [1, 2, 3]. Median is 2