Home Bookmarks Papers Blog

Caveat Emptor - the fact that google returns this page as one of the hits on median computation, does not mean this information is reliable. It is not! A better place to look would be somewhere else (I am too lazy to find the right reference, OK?).

Finding the Median in Linear Time

Let a1, ..., an be n real numbers. We would like to compute their median in linear time. This can be done in linear time by a relatively complicated determinsitic algorithm (see any standard book on data-structures). Luckily, it can be also be done in linear time by the following simple algorithm:

FindKMedian( A, K )

    Return the number in A which is the K-th in its size.
    1. Pick randomly a number a from A = {a1, ..., an}.
    2. Partition the n numbers into two sets:
      • S - all the numbers smaller than a
      • B - all the numbers bigger than a
    3. If |S| = K-1 then a is the required K-median. Return a
    4. If |S| < K-1 then the K-median lies somewhere in B. Call recursively to FindKMedian( B, K - |S| - 1 )
    5. Else, call recursively to FindKMedian( S, K ).
Intuitively, the expected running time of this algorithm is linear because each recursive call takes on the average linear time, and each recursive call reduces the size of the problem by a constant factor.
Back to the linear programming applet