Stony Brook Algorithm Repository


Median and Selection

Input
Output

Input Description: A set of \(n\) numbers or keys.
Problem: Find the item which is smaller than half of the items and bigger than half the items.

Excerpt from The Algorithm Design Manual: Median finding is an essential problem in statistics, where it provides a more robust notion of average than the mean. The mean wealth of people who have published research papers on sorting is significantly affected by the presence of one William Gates [GP-75], although his effect on the {\em median} wealth is merely to cancel out one starving graduate student.

Median finding is a special case of the more general selection problem, which asks for the \(i\)th element in sorted order.


Implementations

libstdc++ (rating 10)
C++ STL (rating 10)
libc++ (rating 9)
Java Collections (rating 9)
Handbook of Algorithms and Data Structures (rating 5)


Recommended Books

Data Streams: Algorithms and Applications by S. Muthukrishnan The Art of Computer Programming : Sorting and Searching by Donald Knuth Compared to What? by G. Rawlins
Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Combinatorial Search by M. Aigner Computer Algorithms by S. Baase
The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman

Related Problems


Priority Queues

Sorting

Go To Main Page