Binary SearchDivide and ConquerArray
Two arrays are each sorted in ascending order. Find the median of all their elements combined, without merging them. The overall run time should be O(log(min(n, m))).
Input
Line 1: n and m. Line 2: n sorted integers. Line 3: m sorted integers.
Output
Print the median with exactly one digit after the decimal point (for example 2.0 or 2.5).
Constraints
1 <= n, m <= 5 * 10^4 -10^6 <= each value <= 10^6
Example 1
Input
2 1 1 3 2
Output
2.0
The merged order is 1 2 3, and the median is 2.
Example 2
Input
2 2 1 2 3 4
Output
2.5
The merged order is 1 2 3 4, so the median is (2 + 3) / 2 = 2.5.