Two sensors each keep their readings sorted in non-decreasing order. Write combined_median(a: list[int], b: list[int]) -> float that returns the median of all the readings together, as if the two lists were merged into one sorted list of length m + n:
- if
m + nis odd, the median is the middle value; - if
m + nis even, it's the average of the two middle values.
combined_median([1, 4, 9], [2, 7]) # 4.0 (merged: 1 2 4 7 9)
combined_median([1, 4], [2, 7]) # 3.0 (merged: 1 2 4 7 -> (2 + 4) / 2)
combined_median([], [5]) # 5.0
combined_median([3, 3, 3], [3, 8, 10]) # 3.0
0 <= m, n <= 10^6,m + n >= 1; values are in[-10^6, 10^6]. Either list may be empty, and values may repeat within and across the lists.- The tests call your function thousands of times on big lists. Merging (or sorting the concatenation) costs O(m + n) per call and is too slow. Aim for O(log(min(m, n))).
- C++ / Java: you write
combinedMedianOfPrefixesAll(a, b, queries). Each query is a pair[i, j](withi + j >= 1) and asks for the combined median of the firstivalues ofaand the firstjvalues ofb. Return the answers in order. Write your median search so it takes the lengths to use, and call it once per query.
Show hint
a cut through a after i values and a cut through b after j values, with i + j equal to half the total, splits everything into a "low half" and a "high half". The cuts are right exactly when nothing on the left of either cut is bigger than anything on the right of the other. Given i, j is fixed, so only i needs searching.