证明：在最坏情况下，利用n + ┌n/2┐ – 2次比较，即可找到n个元素中的第2小元素

思路：折半比较，第一个与最后一个比较，然后第二个与倒数第二个比较，一直进行到中间，最坏情况就是(n+1)/2次比较(n为奇数时)，第二次则是((n+1)/2 + 1)/2，总共有┌lgn┐次

总次数  <=(n/2 + 1/2) + (n/4 + 1/2 + 1/4) + (n/8 + 1/2 + 1/4 + 1/8) ……

=(n/2) * ┌lgn┐ + 1/2 + (1/2 + 1/4) + (1/2 + 1/4 + 1/8) ……

=( ( n/2 ) * (1 – (1/2) ^ ┌lgn┐)) / (1 – 1/2)  + (1/2 + 1/2) + (1/4 + 1/2 + 1/4) + (1/8 + 1/2 + 1/4 + 1/8) + ….. + (1/2) ^ ┌lgn┐

=n – n * (1/2) ^ ┌lgn┐ + ┌lgn┐ – 1 + (1/2) ^ ┌lgn┐

=n + ┌lgn┐ -1 + (1/2) ^ ┌lgn┐ – n * (1/2) ^ ┌lgn┐

<=n + ┌lgn┐ – 1 + (1/2) ^ lgn – n * (1/2) ^ lgn

=n + ┌lgn┐ – 1 + (1 – n) * (1/2) ^ lgn

=n + ┌lgn┐ – 1 + (1 – n) * (1/n)

<=n + ┌lgn┐ – 2