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
⭐ Bonus: a speed test with 100,000 adds, each followed by a median query, earns a star with O(log n) per add_num and O(1) per find_median. Re-sorting on every query is too slow for it.
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.