Loading...
Loading...
Loading...
Two sorted lists of integers are given. Print the median of all their values together, with one decimal place. For an even total, the median is the mean of the two middle values. Use O(log(min(n, m))) time.
Example 1
Input
2 1 1 3 2
Output
2.0
Example 2
Input
2 2 1 2 3 4
Output
2.5
Try the problem first. Open one hint at a time.
Binary search how many items i to take from the shorter list for the left half. The left half then takes j = (n + m + 1) // 2 - i items from the other list.
The split is right when the largest item of the left half is not above the smallest item of the right half, in both lists. Use infinity for a missing side.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor