文章目录【硬核干货】折半查找二分查找ASL 详解为什么失败查找总次数 成功总次数 N一、 核心概念什么是判定树关键性质二、 实战演练手把手算 ASL第一步构建判定树第二步计算 ASL成功第三步计算 ASL失败三、 终极规律为什么失败总次数 成功总次数 N直观理解通俗版严谨推导扩展内部路径长度 EPL四、 总结【硬核干货】折半查找二分查找ASL 详解为什么失败查找总次数 成功总次数 N在数据结构考试中折半查找Binary Search的平均查找长度ASL计算是必考点。很多同学会算成功的 ASL但一遇到“查找失败”就发懵只能苦哈哈地画大树去数空指针。今天我们就来彻底拆解这个问题并揭示一个能帮你秒杀选择题的数学规律失败总比较次数 成功总比较次数 N \text{失败总比较次数} \text{成功总比较次数} N失败总比较次数成功总比较次数N一、 核心概念什么是判定树折半查找的过程可以用一棵二叉树来描述这棵树叫判定树。圆形节点代表数组中的元素查找成功的情况。方形节点或空指针代表查找区间为空查找失败的情况。关键性质节点数如果有N NN个元素就有N NN个圆形节点。空指针数根据二叉树性质度为 0 的节点叶子比度为 2 的节点多 1 个。推导可知N NN个节点的二叉树一定有N 1 N1N1个空指针。所以计算失败 ASL 时分母永远是N 1 N1N1。二、 实战演练手把手算 ASL假设有序数组为[3, 14, 27, 39, 42, 55, 70, 85, 93, 98]共N 10 N10N10个元素。第一步构建判定树我们采用mid (low high) / 2向下取整的规则。第 1 层mid5元素42。第 2 层左边 mid2元素14。右边 mid8元素85。第 3 层14的左边是3右边是27。85的左边是55右边是93。第 4 层27的右边是39。55的右边是70。93的右边是98。(注此处脑补一棵树根是 42层层向下)第二步计算 ASL成功公式∑ ( 每层节点数 × 层数 ) N \frac{\sum(\text{每层节点数} \times \text{层数})}{N}N∑(每层节点数×层数)​第 1 层1 个节点 × 1 次 1第 2 层2 个节点 × 2 次 4第 3 层4 个节点 × 3 次 12第 4 层3 个节点 × 4 次 12总成功次数 1 4 12 12 29 \text{总成功次数} 1 4 12 12 29总成功次数14121229A S L 成功 29 10 ASL_{\text{成功}} \frac{29}{10}ASL成功​1029​第三步计算 ASL失败这是难点。我们需要找到所有的“空指针”失败位置。失败位置总是挂在叶子节点或者只有单孩子的节点下面。怎么数看每个节点的左右孩子是否为空第 3 层的3左右都空 →2 个失败点深度为 3比较 3 次。第 3 层的27左空 →1 个失败点比较 3 次。第 3 层的55左空 →1 个失败点比较 3 次。第 3 层的93左空 →1 个失败点比较 3 次。(目前共 5 个失败点比较次数均为 3)第 4 层的39,70,98这三个都在最底层左右全空。每个节点贡献 2 个失败点。共3 × 2 6 3 \times 2 63×26个失败点。它们的父节点在第 3 层所以走到它们下面是第 4 次比较 →比较 4 次。统计比较 3 次失败的5 个比较 4 次失败的6 个总失败点数5 6 11 5 6 115611(正好是N 1 N1N1)总失败次数 5 × 3 6 × 4 15 24 39 \text{总失败次数} 5 \times 3 6 \times 4 15 24 39总失败次数5×36×4152439A S L 失败 39 11 ASL_{\text{失败}} \frac{39}{11}ASL失败​1139​三、 终极规律为什么失败总次数 成功总次数 N我们在上面算出成功总次数 29失败总次数 39元素个数N NN 10你会发现39 29 10 39 29 10392910。这不是巧合这是一个通用的数学性质直观理解通俗版想象你在走迷宫找宝藏宝藏是成功节点查找成功你找到了宝藏游戏结束。查找失败你走到了一个死胡同空指针。关键点来了任何一个死胡同失败节点都是接在某个宝藏点成功节点后面的。如果你想走进那个死胡同你必须先经过连接它的那个宝藏点的路径。也就是说每一次“失败”的比较路径都包含了一次对应的“成功”比较路径并且在此基础上多走了一步确认这里是空的。虽然有些复杂的树结构会导致层级变化但在**折半查找的判定树近似完全二叉树**中这个规律表现得非常完美每一个失败节点的查找长度≈ \approx≈对应父节点或相关节点的查找长度 1当我们把所有N 1 N1N1个失败情况加起来时大致等于把所有N NN个成功情况加起来再加上N NN次额外的“确认空”的操作。严谨推导扩展内部路径长度 EPL在计算机科学中有一个关于二叉树的定理外部路径长度 (EPL) 内部路径长度 (IPL) 2 × N \text{外部路径长度 (EPL)} \text{内部路径长度 (IPL)} 2 \times N外部路径长度(EPL)内部路径长度(IPL)2×N(注这里的外部路径长度定义通常指根到外部节点的距离之和)但在折半查找的语境下我们的“比较次数”定义略有不同通常指遇到的节点数。对于完全二叉树折半查找树非常接近完全二叉树我们可以简化理解为每一个成功节点共N NN个最终都会导向失败。失败的平均深度总是比成功的平均深度深一层左右。最简单的记忆结论在做选择题时如果你算出了成功查找的总次数分子想验证失败查找的总次数直接加上N NN即可失败分子 成功分子 N \text{失败分子} \text{成功分子} N失败分子成功分子N验证本题成功分子 29N 10 N 10N10预测失败分子 29 10 39 29 10 39291039选项里找分母是 11分子是 39 的 →选 C四、 总结ASL成功∑ ( 层数 × 该层节点数 ) N \frac{\sum(\text{层数} \times \text{该层节点数})}{N}N∑(层数×该层节点数)​ASL失败∑ ( 失败所在层数 × 该层失败数 ) N 1 \frac{\sum(\text{失败所在层数} \times \text{该层失败数})}{N1}N1∑(失败所在层数×该层失败数)​秒杀技巧失败的分母一定是N 1 N1N1。失败的分子≈ \approx≈成功的分子 N NN。掌握这个技巧下次遇到这种题你只需要算出成功的 ASL就能直接推导出失败的 ASL省去了画图和数空指针的巨大麻烦