# 二分查找的平均查找长度 一个有序表的二分查找过程可以记作树形，称为搜索树。树上每个节点代表有序表中的一个元素。这棵树将一定会满足如下条件： - 是一棵二叉排序树 - 除去最深一层后，一定是一棵满二叉树 以整数[1..10]共十个有序数据为例，其搜索树如图所示：  显然，**每个有效节点所处的深度就是它的单点查找长度**；而每个空节点所处的深度要$-1$才是它的单点查找长度（因为空节点不算一次比较，这和哈希表中空节点也计算比较次数是不同的。如果理解不了就想想二分查找的过程，递归到左右位置相同之后还能不能再往下递归了，显然是不能了，这一层递归就是树里的叶子节点，所以叶子节点下的空子节点是没有实际比较的）。 - 查找成功的ASL即为所有有效节点查找长度的平均值，本例中为 $\displaystyle\frac{1+2\times2+3\times4+4\times3}{10}=2.9$； - 查找失败的ASL即为所有空节点查找长度的平均值，本例中为 $\displaystyle\frac{3\times5+4\times6}{11}=\frac{39}{11}$。 > 查找失败时落在每个空节点上的概率显然是不同的，因此不能叫“表元素补集内等概率”，如果有题目讨论等概率情况下查找失败的ASL，那将是不严谨的，我们只好理解为“每种情况等概率”。 > > 查找成功是“表元素集合内等概率”的，同时等价于“每种情况等概率”，没有上述这种问题。 --- 推广到含有$n$个元素的有序表中。 - 先求有效节点的分布情况 - 搜索树的深度为 $\lfloor\log_2n\rfloor+1$ - 除去最深一层后，深度为 $\lfloor\log_2n\rfloor$，是一棵满二叉树，有节点数共 $2^{\lfloor\log_2n\rfloor}-1$ - 单独计算最深一层的节点数为 $N_n=n-2^{\lfloor\log_2n\rfloor}+1$ - 计算倒数第二层开始的满二叉树上单点查找长度的总和 - 对第$i$层（$i$从1开始），其一层有节点数 $2^{i-1}$ - 对全部 $\lfloor\log_2n\rfloor$ 层，有每层节点数$\times$层高，得单点查找长度总和： $$ \displaystyle L_1=\sum_{i=1}^{\lfloor\log_2n\rfloor} 2^{i-1}\cdot i $$ - 单独计算最深一层的单点查找长度的总和： $$ L_2=N_n\times(\lfloor\log_2n\rfloor+1) $$ - 这样即可得到查找成功的平均查找长度： $$\displaystyle ASL_{成功}=\frac{L_1+L_2}{n}$$ - 同理，可得查找失败的平均查找长度： - 空节点总数为 $n+1$ (二叉树性质) - 最深一层有效节点下层的空子节点的单点查找长度总和为 $L_3=2N_n\cdot (\lfloor\log_2n\rfloor+2-1)$ - 与最深一层有效节点同层的空节点的单点查找长度总和为 $L_4=[(n+1)-2N_n]\cdot(\lfloor\log_2n\rfloor+1-1)$ - 得查找失败的平均查找长度： $$ ASL_{失败}=\frac{L_3+L_4}{n+1} $$