Given two sorted lists a and b whose combined length is at least 1, return the median of all their
values as a float. For an even total length the median is the mean of the two middle values.
Examples
Input: a = [1, 3], b = [2]
Output: 2.0
Input: a = [1, 2], b = [3, 4]
Output: 2.5
Input: a = [], b = [7]
Output: 7.0
Constraints
0 <= len(a), len(b) <= 10**6,len(a) + len(b) >= 1-10**9 <= a[i], b[i] <= 10**9- Required time:
O(log(min(len(a), len(b)))). Merging the lists is too slow.
Goals
- Binary search over a partition point of the shorter list
- Use sentinels for partitions at the ends
- Handle even and odd total lengths