7.2.2 折半查找

教材导航 · 第7章

原书定位

印刷页P272起,对应PDF第284页。下文为目视整理的知识提要;完整内容见原书对照。

对有序顺序表维护闭区间 [low,high]。取 mid=low+(high-low)/2,相等即成功;目标较小时令 high=mid-1,较大时令 low=mid+1;low>high 失败。

时间 O(log⁡n)O(\log n),迭代辅助空间 O(1)O(1)。判定树平衡但未必完全;左右子表规模相差至多 1。中点向上或向下取整都可,模拟时必须保持约定一致。

n>0n>0 时最大记录比较次数为 ⌊log⁡2n⌋+1=⌈log⁡2(n+1)⌉\lfloor\log_2 n\rfloor+1=\lceil\log_2(n+1)\rceil。成功 ASL 是各内部结点层数的加权和;失败 ASL 是各外部失败结点父结点层数的加权和。不能把只适用于满判定树的求和公式无条件用于任意 nn。

折半查找判定树与失败区间

折半查找判定树与失败区间,原书P273。

对应练习

7.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P272,PDF第284页

原书对照,原书P273,PDF第285页