Binary Search · 019Hard
Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array. The overall run time must be O(log(m + n)).
Constraints
- 0 <= m, n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
Examples
findMedianSortedArrays([1, 3], [2]) -> 2.0 findMedianSortedArrays([1, 2], [3, 4]) -> 2.5 // (2 + 3) / 2 findMedianSortedArrays([], [1]) -> 1.0 // nums1 empty findMedianSortedArrays([1, 2, 3], []) -> 2.0 // nums2 empty findMedianSortedArrays([1, 3], [2, 7]) -> 2.5 // interleaved, even total length findMedianSortedArrays([0, 0], [0, 0]) -> 0.0 // duplicates
Edge cases
- Either array may be empty.
- Even total length averages the two middle values.
Show the target complexity (spoiler)
- Naive
- O(m + n) time — merge both arrays and index the middle. Fails the required
- Target
- O(log(min(m, n))) time, O(1) space — binary search for the partition where every left element <= every right element.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/05-binary-search/019-median-of-two-sorted-arrays.js ./practice c 019