# The Stony Brook Algorithm Repository

## 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.

## 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