Problem: Median of a Data Stream

Numbers arrive one at a time, and after each one arrives we have to report the median of everything seen so far.

The median is the middle of the sorted order. When the count is odd there is a single middle value. When the count is even there are two middle values, and the median is their average.

Here is the interface:

/**
 * A MedianFinder takes in a stream of integers, one at a time, and reports the
 * median of every value seen so far.
 */
public interface MedianFinder {
  /**
   * Takes in the next value from the stream.
   * @param value the next number in the stream
   */
  void add(int value);

  /**
   * Returns the median of all values added so far. When the count is even,
   * this is the average of the two middle values.
   * @return the current median of the stream
   * @throws NoSuchElementException if no values have been added yet
   */
  double median();
}

median() returns a double because of the even case: the average of two integers can have a fractional part of one half, like 3.5.

Take the stream 5, 2, 8, 1, 9, 3. Each line shows the number that arrives, everything seen so far in sorted order, and the median:

arrives   seen so far (sorted)   median
5         5                      5
2         2 5                    (2 + 5) / 2 = 3.5
8         2 5 8                  5
1         1 2 5 8                (2 + 5) / 2 = 3.5
9         1 2 5 8 9              5
3         1 2 3 5 8 9            (3 + 5) / 2 = 4

Try the most direct solution first, then look for one that does less work.