Two branches each hand Arif a separately sorted list of book IDs, and he needs the MEDIAN of the combined collection, fast, without physically merging both lists. Given two sorted arrays of sizes N and M, find the median of the combined array. You MUST achieve O(log(min(N,M))) time (binary searching the partition point) — a full merge is too slow for the intended constraints.
Input
Line1: N M. Line2: N sorted integers. Line3: M sorted integers.
Output
The median, printed with 1 decimal place if it's a .5 value, otherwise as an integer.
Constraints
1 ≤ N, M ≤ 10^6
Sample Input
2 3 1 3 2 4 5
Sample Output
3.0
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.