Median of a stream

Values arrive one at a time. After any of them, you may be asked for the median of all values so far: the middle value once they are sorted, or the average of the two middle values when the count is even. Return it as a float.

m = MedianFinder()
m.add(5);  m.median()    # 5.0
m.add(15); m.median()    # 10.0
m.add(1);  m.median()    # 5.0
m.add(3);  m.median()    # 4.0

median is only called after at least one add. Values are integers and can repeat.

The modules heapq and bisect are switched off.

One test passes in numbers that count how often they are compared with <, <=, > or >=. They behave like ordinary numbers otherwise. This is how the tests tell an O(log n) heap step from an O(n) scan, which a timer cannot always do.

Limits

• Up to 50,000 values, with a median after each. add should take O(log n) comparisons and median O(1).