Find the Doubled Median of Two Sorted Arrays via Partitioning
Implement findDoubledMedian
Given two sorted arrays
nums1 and nums2, find the median of all the elements combined — without necessarily merging them — returned as double its true value so the answer is always a whole number.
Merging both arrays and reading off the middle works, but it does far more than necessary: only one or two values near the middle actually matter for the answer, yet the full combined array gets built regardless. The faster approach searches directly for a valid split point instead: a cut in the smaller array, paired with a matching cut in the larger one, such that together they divide all the elements into a "left half" and a "right half" of equal size, with every left value at most every right value. Binary search finds that cut in O(log(min(m,n))) guesses — checking just four boundary values per guess — and once a valid split is found, the median is read directly off those boundaries, with the merge step skipped entirely.
Example 1:
Input: nums1 = [3,9,15], nums2 = [6,12]
Output: 18
Example 2:
Input: nums1 = [4,10], nums2 = [1,7,13,19]
Output: 17
Example 3:
Input: nums1 = [1,2,3], nums2 = [4,5,6,7]
Output: 8
+ 3 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums1.length, nums2.length ≤ 6 - ●
-100 ≤ nums1[i], nums2[i] ≤ 200 - ●
Both arrays are sorted in non-decreasing order - ●
Return double the true median, so the answer is always a whole number (avoiding any floating-point comparison)
nums1 =
[3, 9, 15]
nums2 =
[6, 12]