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

### Related Problems

 Priority Queues Sorting

Go To Main Page