Implement a class MedianFinder that receives numbers one at a time and can report the median of everything seen so far:
MedianFinder()starts empty.add_num(x)records the integerx.find_median()returns the median as afloat: the middle value when the count is odd, or the average of the two middle values when it is even. It is only called after at least oneadd_num.
mf = MedianFinder()
mf.add_num(10)
mf.find_median() # 10.0
mf.add_num(4)
mf.find_median() # 7.0
mf.add_num(6)
mf.find_median() # 6.0
The tests interleave up to 100,000 adds with a median query after each one, so re-sorting on every query is far too slow. Aim for O(log n) per add_num and O(1) per find_median.
Show hint
Split the numbers seen so far into a lower half and an upper half. You only ever need the largest of the lower half and the smallest of the upper half, and the halves must stay balanced in size.