Median of Two Sorted Lists

a and b are each sorted in increasing order, and together they hold at least one value. Return the median of all their values combined, as a number with a decimal point (3.0, 2.5). For an even count the median is the average of the two middle values.

Merging and sorting works, but reads everything. The big tests only allow a few hundred reads.

Examples

Example 1

Input:

median_two_sorted([1, 3], [2])

Output:

2.0

Combined: 1, 2, 3. The median is 2.

Example 2

Input:

median_two_sorted([1, 2], [3, 4])

Output:

2.5

Combined: 1, 2, 3, 4. The median is (2 + 3) / 2 = 2.5.

Constraints

• 1 <= len(a) + len(b) <= 4 * 10**5
• Both lists are sorted in non-decreasing order.
• -10**9 <= value <= 10**9
• The big tests count how many values you read from each list.