Median of Two Sorted Arrays

Given two sorted arrays, find the median of all their values combined. (The median is the middle value of the sorted combination; with an even count it is the average of the two middle values.)

Input:

• line 1: m n
• line 2: the m values of the first array (empty if m = 0)
• line 3: the n values of the second array (empty, or missing, if n = 0)

Output: the median with exactly one digit after the decimal point, for example 2.0 or -2.5. (The median of integers always ends in .0 or .5.)

Constraints: 0 ≤ m, n ≤ 10⁵, 1 ≤ m + n, −10⁶ ≤ value ≤ 10⁶. Tip: read all numbers as whitespace-separated tokens to handle empty lines easily.

Challenge: merging is O(m + n) and passes here — the famous interview version asks for O(log(min(m, n))): binary search a cut in the smaller array so that everything left of both cuts is ≤ everything right of them.