一、二分查找平均查找长度计算

1、例题

有序序列：15、29、36、56、66、78、90
1）构造一颗查找树
2）求出29的查找次数
3）求出平均查找长度
解：
1）

给每个数编号

1 2 3 4 5 6 7
15 29 36 56 66 78 90

L=1,R=7, M=(L+R)/2 = 4

所以第一次，查出来的是4号，对应的值是56，故：56的查找次数是1，且是根节点（第一层节点）

L=1,R=3, M=(L+R)/2 = 2

所以第二次，查出来的是2号，对应的值是29，故：29的查找次数是2，且是第二层节点
因为对称性，6号对应值78，查找次数也是2，且是第二层节点

L=1,R=1, M=(L+R)/2 = 1

所以第三次，查出来的是1号，对应的值是15，故：15的查找次数是3，且是第三层节点
因为对称性，3号对应值36，5号对应值66，7号对应值90，
查找次数也是3，且是第三层节点
构造的树如下：

2）根据1）所得，查找次数是2
3）平均查找长度 ASL = 每个节点查找的次数和/ 节点数
节点数为 n=7
每个节点查找的次数和 S = 1x1+2x2 + 3x4
ASL = S/n= 17/7

2、注意

1）M的取值，是取整函数
2）R和L的取值，除了第一次，是根据第一次M值，进行+1 或 -1操作
3）利用对称性，可以快速推出查找次数，同时查找次数可以看出是查找二叉树的对应层数
4）平均查找长度 ASL = 每个节点查找的次数和/ 节点数

二、推倒二分查找时间复杂度为什么是 log2n

1、预备知识

1）等比数列求和公式

其中：
a1是首项，
an是末项，
q是等比
2）如果二叉树的层数是h，则整棵树最多的节点数 n = 2 -1，可推导出 h = log(n+1)
举例：二叉树层数是3，满二叉树节点个数是 7
3）如果是二叉树的第i 层，则这层的节点数最多是 maxi = 2
举例：二叉树第3层，满二叉树第三层节点个数是 4

2、推导过程

1）用一颗满二叉树来推导
2）设树的高度是h，树的所有节点是n
3）由预备知识2）可推出 h = log(n+1)
4）假设每个元素的查找概率相同，pi = 1/n （pi为第i个节点的查找概率）
5）每个节点的查找次数 = 层数，每层的节点数是 2
6）平均查找长度：ASL = pi x S = (1x2 + 2x2+ 3x2+ … + hx2) / n
7）化简 :
化简 S ：
S = 1x2 + 2x2+ 3x2+ … + hx2
2S = 1x2 + 2x2+ … + (h-1)x2 + hx2h
S-2S = 1 + 2 +2+ … +2+ hx2h
-S = (1 - 2h)/(1-2) + hx2h ( 等比数列求和公式）
S = 1- 2h + hx2h
= 1+(h-1) 2h

化简 ASL ：
因为：h = log(n+1) ，将h带入
ASL = （1+(h-1) 2h）/n
= （1+（ log(n+1)-1）x（n+1）） /n
= [(n+1) -n +（ log(n+1)-1）x（n+1）]/n
= [（n+1）log(n+1)-n ] /n
= [(n+1)/n]log(n+1) -1