7.2.2 折半查找
原书定位
印刷页P272起,对应PDF第284页。下文为目视整理的知识提要;完整内容见原书对照。
对有序顺序表维护闭区间 [low,high]。取 mid=low+(high-low)/2,相等即成功;目标较小时令 high=mid-1,较大时令 low=mid+1;low>high 失败。
时间 ,迭代辅助空间 。判定树平衡但未必完全;左右子表规模相差至多 1。中点向上或向下取整都可,模拟时必须保持约定一致。
时最大记录比较次数为 。成功 ASL 是各内部结点层数的加权和;失败 ASL 是各外部失败结点父结点层数的加权和。不能把只适用于满判定树的求和公式无条件用于任意 。

折半查找判定树与失败区间,原书P273。
对应练习
关联知识
- 2.2.2 顺序表上基本操作的实现
- 5.3.1.2 中序遍历
- 7.2 顺序查找和折半查找
- 7.2.1 一般线性表的顺序查找
- 7.2.1.1 有序线性表的顺序查找
- 7.2.3 分块查找
- 7.3.1 二叉排序树的定义
- 8.1 排序的基本概念
- 8.2.1 直接插入排序
- 8.2.2 折半插入排序
- 8.3.2 快速排序
- 8.5.1 归并排序
原书对照
展开原书对照截图

