The middle of two sorted lists
Find the median of two sorted lists without merging them, by searching for the cut in the shorter list. About 20 minutes.
Cut both lists
The median is the middle value of everything. Cut both sorted lists once, and put the left pieces together as the lower half and the right pieces together as the upper half. The lower half must hold half of all the values, rounded up, so choosing the cut in one list forces the cut in the other.
A cut is correct when every value in the lower half is at most every value in the upper half. Since each list is sorted already, only the values next to the cuts need checking.
total = len(a) + len(b) half = (total + 1) // 2 # left side
Try one value of a in the lower half, so three of b. The lower half is 2, 1, 6, 8. But 8 in the lower half is bigger than 4, the first upper value of a. The cut in a is too far left.
Search the cut
Search the cut in the shorter list, so the other cut never goes out of range. Let i values of a go to the lower half, so half minus i values of b do too. Look at the four neighbours: the last of a's lower part, the first of a's upper part, and the same for b.
If a's last lower value is bigger than b's first upper value, a's cut is too far right, so move it left. If b's last lower value is bigger than a's first upper value, a's cut is too far left. Otherwise the cut is right, and the median comes from the neighbours.
Why do we search the cut in the shorter list?
- ASo the matching cut in the longer list never falls outside it
- BOnly because it is faster
- CIt doesn't matter which one
Show the answer
So the matching cut in the longer list never falls outside it. The lower half has a fixed size, so with a shorter list the other cut stays in range.
Twice the median
a and b are two lists of whole numbers, each sorted from smallest to largest, and together they hold at least one value. Imagine merging them into one sorted list. Return twice its median: if the merged list has an odd length, that is twice the middle value, and if it has an even length, it is the sum of the two middle values.
a = [1, 3, 8], b = [2, 7] → 6
0 ≤ length of each list ≤ 100,000 · at least one value in total · −1,000,000,000 ≤ value ≤ 1,000,000,000