hardBinary SearchPure DSA~40 min
Merge Shard Median
Two database shards each return a sorted slice of a metric. You need the median of the combined dataset without materialising the full merge — in logarithmic time.
Problem
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)).
Input
Two sorted arrays nums1 (size m) and nums2 (size n), 0 ≤ m+n, values 32-bit.
Output
A floating-point number — the median of the union.
Constraints
- Target O(log(min(m, n))) time — do not merge fully
- 0 ≤ m, n and 1 ≤ m + n
- Median of an even total is the average of the two middle values
Examples
Example 1
Input
nums1 = [1,3], nums2 = [2]
Output
2.0
Merged = [1,2,3]; median is 2.
Example 2
Input
nums1 = [1,2], nums2 = [3,4]
Output
2.5
Merged = [1,2,3,4]; median = (2+3)/2.