Question

二叉树的折半查找怎么算？

Answer 1

首先，折半查找可以借助于一个二叉树来描述。
为了简化讨论，则把这棵树近似看成满二叉树，设二叉树的高度为h(h>1)
则，根据二叉树的性质，它有最大节点数n=2^h-1，
则h=log2(n+1) (2是底数)。那么二叉树的第j层节点数为：2^(j-1)
假定每个元素的查找概率相等，则，pi=1/n (pi为第i个节点的查找概率)
那么平均查找长度为 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）
则经过化简计算，得平均查找长度为：(（n+1）/n ) *log2(n+1)-1 (其中对数中的2为底数：即log以2为底（n+1)的对数）
注 : 当n很大时 ，可近似为 log2(n+1)-1
其中 1*2^0+2*2^1+3*2^2+……+j*2^(j-1)的求法如下：
设 S = 1*2^0 + 2*2^1+3*2^2 +……+ j*2^(j-1) ,
则 2S = 1*2^1+2*2^2 +……+ (j-1)*2^(j-1) + j*2^j
则 2S - S = -( 2^0 + 2^1 + 2 ^2 + …… + 2 ^(j-1)) + j *2^j
即 S = - (2^j-1)+j*2^j
带入化简即可。