Median selection requires (2+ϵ)n comparisons

Improving a long standing result of Bent and John (1985), we obtain a (2+ε)n lower bound (for some fixed ε>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