ALG-H001HardBinary Search
Median Across Sorted Streams
Two non-decreasing integer arrays are given and at least one is non-empty. Return the median of all their values, as a number, without relying on a complete merge for the intended optimal approach.
Contract
input a: integer[]
input b: integer[]
return number
Constraints
- • Both arrays are sorted
- • Combined length >= 1
Examples
Example 1
a = [1, 3]
b = [2]
→ 2
Example 2
a = [1, 2]
b = [3, 4]
→ 2.5
5 judge tests (2 shown above). Target complexity: O(log(min(m,n)+1)).