查找是在一组记录中定位目标。算法效率取决于数据是否有序、能否随机访问、更新是否频繁，以及一次比较或访存的成本。

本章用三个问题串起常见查找结构：

1. 范围怎样缩小？ 顺序查找逐个排除，折半查找每次排除一半；
2. 有序性怎样维持？ BST、AVL、红黑树和 B 树用结构不变量支撑动态查找；
3. 能否直接计算位置？ 散列表放弃全局次序，以冲突处理换取平均常数时间。

学习目标

完成本章后，你应该能够：

• 区分静态查找表与动态查找表，用平均查找长度（ASL）衡量比较代价；
• 手算顺序查找、分块查找和折半查找的比较次数，解释折半判定树；
• 完成 BST 的查找、插入和三类删除，判断插入顺序为何会造成退化；
• 根据失衡形态选择 AVL 的 LL、RR、LR、RL 调整，并说明红黑树的工程取舍；
• 判断 m 阶 B 树的结点上下界，推演分裂、借键与合并，比较 B 树和 B+ 树；
• 构造开放定址或链地址散列表，计算成功与失败 ASL，并分析装填因子的影响；
• 根据查询类型、更新频率、顺序需求和存储层次选择合适结构。

理论框架

层次	核心约束	典型结构	查找代价从哪里来
线性查找	可无序；顺序访问即可	顺序查找	已检查元素的数量
有序静态表	有序且支持随机访问	折半查找	判定树深度
分级索引	块间有序、块内可无序	分块查找	索引查找 + 块内查找
动态有序表	插删后仍保持次序	BST、AVL、红黑树	树高
外存多路索引	一个结点容纳多个关键字	B 树、B+ 树	树高与 I/O 次数
地址计算	允许牺牲全局次序	散列表	冲突与探测/链长

统一分析法

先写出结构成立的前提，再确定一次查找经过哪些位置，最后计算路径长度或比较次数。只背 O(log n)、O(1)，很容易漏掉退化条件和统计口径。

五篇文章如何分工

学习问题	对应文章	完成后的可检查能力
静态表中怎样查找并计算 ASL？	8.1 基础查找与折半查找	能画折半判定树并比较顺序、分块、折半查找
动态有序集合怎样增删查？	8.2 二叉排序树	能处理 BST 三类删除并分析退化
怎样把树高稳定在对数级？	8.3 平衡查找树	能判断 AVL 旋转并解释红黑树性质
数据在磁盘上时怎样减少 I/O？	8.4 B 树与 B+ 树	能计算结点边界并推演分裂、借键和合并
不比较关键字能否直接定位？	8.5 散列表	能构造探测序列并计算成功/失败 ASL

推荐学习顺序

1. 从基础查找与折半查找建立 ASL、判定树和比较次数的统一语言。
2. 学习二叉排序树，观察静态的折半思想如何变成动态树结构。
3. 继续学习平衡查找树，理解“修复局部结构”如何换来最坏情况保证。
4. 在B 树与 B+ 树中把二叉搜索推广到多路搜索，并把成本单位换成磁盘 I/O。
5. 最后学习散列表，比较“维护次序”和“直接计算地址”两条路线。
6. 完成操作 Lab 后，用历年理论题做一次跨主题自测。

配套 Labs

• Lab 08-T-01：查找理论选择题精练
• Lab 08-E-01：BST 增删查与边界测试
• Lab 08-P-01：自平衡查找树——AVL 旋转维护与退化对比
• Lab 09-T-01：散列与索引选择题精练
• Lab 09-E-01：散列表实现与冲突统计
• Lab 09-P-01：散列索引引擎——冲突策略与再散列大综合

选型时先问什么

问题	更合适的起点
数据量小，或只查一次	顺序查找
数据基本不变、已有序且能随机访问	折半查找
只需要粗粒度索引，块内更新方便	分块查找
需要动态插删、范围查询和有序遍历	平衡搜索树
数据主要位于磁盘或页式存储	B+ 树
主要做精确匹配，不要求有序	散列表

交互式演示

本章的部分页面嵌入了可交互演示，用来把抽象结构变成能一步步观察的过程：

• 折半查找 · 判定树（8.1）：手动走查找，看 low/mid/high 如何每次砍掉一半，并同步生成判定树。
• 二叉排序树 · 退化与删除（8.2）：用不同插入顺序对比树形与 ASL，点结点看三类删除。
• AVL 树 · 旋转实验室（8.3）：观察平衡因子，逐键插入触发 LL/RR/LR/RL 旋转。
• 散列表 · 冲突与 ASL（8.5）：比较线性探测与链地址，实时统计成功/失败 ASL。

准备好后，从8.1 基础查找与折半查找开始。你想先动手，翻到对应页面点开演示即可。