Appearance
折半查找（二分查找）
O(log n) 的查找效率
顺序查找从头到尾扫一遍，1000 个元素最多比较 1000 次。折半查找利用有序性每次砍掉一半，1000 个元素最多只需 10 次比较——这就是 O(n) 和 O(log n) 的差距。
408 考研中，折半查找是查找章节的核心，高频考查，需要掌握算法流程、判定树构造、ASL 计算等全部内容。
前提条件：折半查找要求表必须是有序的顺序表（即用数组存储的有序序列）。
核心思想
折半查找的核心特点：
- 每次比较排除一半：将查找区间缩小为原来的一半
- 三个指针：用
low、high标记当前查找区间，mid = (low + high) / 2为中间位置 - 比较与缩小区间：将目标值
key与mid位置元素比较，相等则查找成功；key较小则在左半区间继续查找；key较大则在右半区间继续查找 - 终止条件：
low > high时查找失败
交互可视化
通过下方的交互动画，你可以逐步观察折半查找的执行过程：
操作详解
算法思路
关键步骤：
- 初始化
low = 0，high = n - 1 - 计算
mid = (low + high) / 2（向下取整） - 比较
key与a[mid]：- 若
key == a[mid]，查找成功，返回mid - 若
key < a[mid]，令high = mid - 1，在左半区间继续 - 若
key > a[mid]，令low = mid + 1，在右半区间继续
- 若
- 重复步骤 2-3，直到
low > high，查找失败
代码实现：
c
// 折半查找（非递归）
// a[] 为有序数组（升序），n 为元素个数，key 为目标值
int BinarySearch(int a[], int n, int key) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == key)
return mid; // 查找成功
else if (a[mid] > key)
high = mid - 1; // 在左半区间查找
else
low = mid + 1; // 在右半区间查找
}
return -1; // 查找失败
}注意
mid的取整方向：(low + high) / 2是向下取整（取左中位数）。不同取整方式会构造出不同的判定树，408 真题中经常以此设陷阱。
易错：
mid = ⌊(low+high)/2⌋（向下取整）和mid = ⌈(low+high)/2⌉（向上取整）会构造出不同形态的判定树，导致 ASL 不同。408 默认向下取整，但真题中偶尔会指定向上取整来设陷阱。做题时建议先确认取整方式。
判定树构造
折半查找的过程可以用一棵判定树（也叫比较树）来描述。每个结点表示一次比较的中间元素 mid，左子树对应 key < a[mid] 的情况，右子树对应 key > a[mid] 的情况。
以有序表 {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43} （n = 11）为例，判定树如下：
第一次比较：low = 0，high = 10，mid = (0 + 10) / 2 = 5，即 a[5] = 29 作为根。左半区间 {7, 10, 13, 16, 19}、右半区间 {32, 33, 37, 41, 43} 再分别递归取中，得到：
[29] ← 第 1 层
/ \
[13] [37] ← 第 2 层
/ \ / \
[7] [16] [32] [41] ← 第 3 层
\ \ \ \
[10] [19] [33] [43] ← 第 4 层第 3 层的 7、16、32、41 都来自只剩 2 个元素的区间（如
{7, 10}：mid 向下取整取到 7，10 进入右子树），所以它们都只有右孩子。
对照：改用向上取整会得到什么树？
同一序列、mid = ⌈(low + high) / 2⌉：奇数长度的区间取的中点不变（根仍是 29，第 2 层仍是 13、37），但 2 个元素的区间会取到靠右的那个（{7, 10} 取 10，7 进入左子树），整棵树变成向下取整树的镜像：
[29] ← 第 1 层
/ \
[13] [37] ← 第 2 层
/ \ / \
[10] [19] [33] [43] ← 第 3 层
/ / / /
[7] [16] [32] [41] ← 第 4 层两棵树每层结点数相同，所以本例的成功/失败 ASL 都不变；但具体某个元素的比较次数变了——查 10：向下取整树要 4 次（29→13→7→10），向上取整树只要 3 次（29→13→10）。真题问"查找 X 需要比较几次"时，取整方向直接决定答案，这就是命题人埋陷阱的位置。
判定树的重要性质：
- 判定树是一棵平衡二叉排序树（形态唯一，取决于 n 和取整方式）
mid = ⌊(low + high) / 2⌋时，若结点数为偶数，左子树结点数比右子树少 1（右子树结点数更多）；若为奇数则左右相等- 树的高度 h = ⌈log₂(n+1)⌉
- 查找成功时的比较次数 = 该元素在判定树中的层数
- 查找失败时的比较次数 = 走到的外部结点（空结点）的父结点层数
ASL 计算
查找成功的 ASL
假设查找每个元素的概率相等（均为 1/n），则：
其中
以上面 n = 11 的例子为例：
| 层数 | 结点 | 结点数 |
|---|---|---|
| 1 | 29 | 1 |
| 2 | 13, 37 | 2 |
| 3 | 7, 16, 32, 41 | 4 |
| 4 | 10, 19, 33, 43 | 4 |
通用公式（n 较大时的近似值）：
易错：查找成功的 ASL 分母是 n（元素个数），查找失败的 ASL 分母是 n+1（外部结点个数，即失败区间数）。很多同学在计算失败 ASL 时错误地用 n 做分母。
查找失败的 ASL
查找失败时，查找路径终止于判定树的外部结点（即空指针位置，共 n+1 个）。每个外部结点对应一个失败的查找区间，比较次数等于其父结点的层数（即路径上经过的内部结点数）。
仍以 n = 11 为例，外部结点共 12 个。下面逐一推导每个失败区间的比较次数：
逐区间推导查找失败比较次数：
| 失败区间 | 探测路径（沿判定树） | 比较次数 |
|---|---|---|
| key < 7 | 29→13→7→左空 | 3 |
| 7 < key < 10 | 29→13→7→10→左空 | 4 |
| 10 < key < 13 | 29→13→7→10→右空 | 4 |
| 13 < key < 16 | 29→13→16→左空 | 3 |
| 16 < key < 19 | 29→13→16→19→左空 | 4 |
| 19 < key < 29 | 29→13→16→19→右空 | 4 |
| 29 < key < 32 | 29→37→32→左空 | 3 |
| 32 < key < 33 | 29→37→32→33→左空 | 4 |
| 33 < key < 37 | 29→37→32→33→右空 | 4 |
| 37 < key < 41 | 29→37→41→左空 | 3 |
| 41 < key < 43 | 29→37→41→43→左空 | 4 |
| key > 43 | 29→37→41→43→右空 | 4 |
按比较次数汇总：
| 父结点层数 | 外部结点数 |
|---|---|
| 3 | 4 |
| 4 | 8 |
第 3 层的 7、16、32、41 四个结点都只有右孩子，各贡献 1 个空的左子树（即 4 个"比较 3 次"的外部结点）。其余 8 个外部结点均来自第 4 层叶结点（10、19、33、43）各自的两个空子树。
408 考试中 ASL 计算是高频大题，建议能够根据给定序列手画判定树，然后逐层统计结点数。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间复杂度 | O(1) | 第一次比较就命中（mid 恰好是目标） |
| 最坏时间复杂度 | O(log₂n) | 比较次数等于判定树高度 ⌈log₂(n+1)⌉ |
| 平均时间复杂度 | O(log₂n) | ASL ≈ log₂(n+1) - 1 |
| 空间复杂度 | O(1) | 仅需 low、high、mid 三个辅助变量 |
为什么链表不能使用折半查找？
折半查找的关键在于需要随机访问 a[mid]，即通过下标直接定位中间元素（O(1) 时间）。链表不支持随机访问，访问第 mid 个结点需要从头遍历，时间为 O(n)，这会使折半查找退化为比顺序查找更慢的算法，失去意义。因此折半查找仅适用于顺序表（数组）。
易错：折半查找要求有序 + 顺序存储，两个条件缺一不可。有序链表不能用折半查找（不支持随机访问），无序数组也不能用（无法利用有序性缩小区间）。
本文对应考点
- 给定有序序列，手动画判定树并计算成功 / 失败 ASL（大题高频，高频考查）
- 折半查找的适用条件：有序 + 顺序存储（选择题高频陷阱）
- 判定树的形态与 mid 取整方式的关系（向下取整 vs 向上取整构造不同的树）
- 折半查找的时间复杂度 O(log₂n) 及其推导
- 折半查找与二叉排序树的对比（判定树是平衡 BST）
- 折半查找失败时比较次数的计算（外部结点分析）
- 为什么链表不适用折半查找（随机访问特性）
相关知识
- 折半查找的判定树是一棵平衡二叉排序树，与 AVL 树的平衡性质相呼应——理解判定树有助于理解平衡树的高度分析
- 折半查找要求有序 + 顺序存储，如果数据频繁插入删除，维护有序性代价高，此时应考虑 二叉排序树（BST）或 B 树等动态查找结构
- 折半查找的 ASL 计算方法（按层统计）也适用于 BST 的 ASL 分析，两者的分析框架完全一致