折半查找

成功

最多比较次数(高度)

$$ H = \lceil \log_2(n + 1) \rceil $$

最少比较次数:1

失败

比较次数

$$ 满二叉树 【 n = 2^h - 1 】 次数为h $$

$$ 非满二叉树 【 n\neq 2^h - 1 】 次数为h-1 $$

折半平均查找长度

小规模可以直接画出判定树再进行计算

大规模直接用公式 算出有多少层 每层有多少个元素 再计算ASL

计算失败asl时要先画出失败节点 因为失败节点是虚假的节点 其实检查到它的父节点就结束了 所以要减去1

$$ ASL(成功)=∑(比较次数×该层结点数)/n $$

$$ ASL(失败)=∑((所在层数-1)×该层结点数)/n $$

最后修改:2026 年 07 月 26 日