 |
 |
|
|
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) |
  Priority Queues |
  Sorting |
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
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