Median selection requires (2+ε)n comparisons
David H. Ben Dor, Uri Zwick · 2002
Improving a long standing result of Bent and John (1985), we obtain a (2+/spl epsiv/)n lower bound (for some fixed /spl epsiv/>0) on the number of comparisons required, in the worst case, for selecting the median of n elements. The new lower bound is obtained using a weight function that allows us to combine leaf counting and adversary arguments.