INPUT OUTPUT

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

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 |

This page last modified on 2008-07-10 . www.algorist.com