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.

libstdc++ (rating 10) |
C++ STL (rating 10) |

libc++ (rating 9) |
Java Collections (rating 9) |

Handbook of Algorithms and Data Structures (rating 5) |