在假定每个结点的查找概率相同的情况下,二分检 索的平均查找次数为 ASL bins (1·2+2·2+32+…+i·2+..+k.2-) 用数学归纳法容易证明:∑12=2(k-1)+1 ASL bins (2·(k-1)+1)=-(n+1)(og2(m+1)-1)+1) =lg2(n+1)-1+-log2(m+1) n =log2(n+1)-1(1 2 2 2 3 2 ... 2 ... 2 ) 1 0 1 2 −1 −1  +  +  + +  + +  i k i k n ASLbins= 在假定每个结点的查找概率相同的情况下，二分检 索的平均查找次数为： 2 2 ( 1) 1 1 1   = − + = − i k k k i i 用数学归纳法容易证明： (( 1)(log ( 1) 1) 1) 1 (2 ( 1) 1) 1 2   − + = n + n + − + n k n k ASLbins= log ( 1) 1 log ( 1) 1 2 + − + 2 n + n = n = log2 (n+1)-1