折半查找
成功
最多比较次数(高度)
$$ 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 $$