Median of Two Sorted Lists

a and b are lists of numbers, each sorted in ascending order. Write median_two_sorted(a, b) that returns the median of all the numbers from both lists together, as a float. The median is the middle value when the count is odd, and the average of the two middle values when it is even. One of the lists can be empty, but not both.

Examples

median_two_sorted([1, 4, 9], [2, 3])   # returns 3.0
median_two_sorted([1, 4], [2, 3])      # returns 2.5
median_two_sorted([], [7])             # returns 7.0

Together, the first example holds 1, 2, 3, 4 and 9, so the middle value is 3. The second holds 1, 2, 3 and 4, and the average of 2 and 3 is 2.5.

Constraints

• 0 <= len(a), len(b) <= 100,000
• 1 <= len(a) + len(b)
• -10^6 <= a[i], b[i] <= 10^6

Note

Merging the lists passes these tests. The real challenge is to find the median in a number of steps that grows with the logarithm of the shorter list's length, without walking through the lists at all.