查找算法分析与对比

2026 大纲 六（九）查找算法的分析及应用。本篇是整章的总结。

一整章其实只有三条路

查找方法看着有十来种，但它们回答的是同一个问题：怎样用尽可能少的代价，把候选范围压到 1。压缩范围的手段只有三种，于是也就只有三条技术路线。

第一条：靠比较，在线性表上排除。 每比较一次排除掉一部分候选——顺序查找排除 1 个，折半查找排除一半，分块查找排除一整块。代价是折半要求有序 + 随机存取，只能用在静态顺序表上。

第二条：靠比较，但把分支结构存下来。 把"排除一半"固化成树的分支——BST、AVL、红黑树、B 树、B+ 树。代价是额外的指针空间和维护平衡的开销，换来的是在 $O(\log n)$ 的同时支持插入删除。

第三条：干脆不比较。 散列表由关键字直接算出地址，一次计算代替一串比较。代价是彻底失去有序性。

一句话概括三条路的取舍：线性表用简单换效率，树表用空间和维护代价换动态性，散列表用有序性换速度。

这三条路是递进的：顺序 $O(n)$ → 折半 $O(\log n)$ 但只能静态 → 树表 $O(\log n)$ 且能动态 → 散列 $O(1)$ 但放弃有序。每往前一步都在拿掉一样东西，看清拿掉的是什么，选型就不会错。

⚠️ 树形查找（六（五））与字符串模式匹配（六（八））按大纲都属于「查找」，但本站分别编排在树、串两组里。本篇的对比表把树形查找一并纳入；字符串模式匹配的"查找对象"是子串、比较单位是字符，不适用 ASL 那一套，故不在对比表内（见《BF 算法》与《KMP 算法》）。

先动手看一眼

加载可视化中...

总表：适用条件 · ASL · 有序性 · 动态性

四栏分别对应选型时要问的四个问题。

查找方法	存储结构要求	是否要求有序	平均查找长度	支持动态增删	展开
顺序查找（无序表）	顺序表或链表均可	否	成功 $\frac{n+1}{2}$；失败 $n$ 或 $n+1$	✅ 直接追加	→
顺序查找（有序表）	顺序表或链表均可	是	成功 $\frac{n+1}{2}$；失败 $\frac{n}{2}+\frac{n}{n+1}$	⚠️ 要维持有序，插入需移动	→
折半查找	必须顺序表（要随机访问）	必须有序	成功 $\approx {\log }_2(n+1)-1$；失败 $\approx {\log }_2(n+1)$	❌ 不支持	→
分块查找	顺序表 + 索引表	块间有序，块内无序	顺序索引最优 $\sqrt{n}+1$	✅ 块内随便放	→
二叉排序树（BST）	二叉链表	中序有序	平均 $O({\log }_{2}n)$；最坏 $O(n)$	✅	→
平衡二叉树（AVL）	二叉链表 + 平衡因子	中序有序	$O({\log }_{2}n)$，最坏也是	✅（插删可能触发旋转）	→
红黑树	二叉链表 + 颜色位	中序有序	$O({\log }_{2}n)$，树高 $\le 2{\log }_2(n+1)$	✅（调整次数比 AVL 少）	→
B 树	多路平衡查找树（外存）	是	$O({\log }_{\lceil m/2\rceil }n)$ 次磁盘 I/O	✅（分裂/合并）	→
B+ 树	多路平衡树 + 叶结点链表	是	同上，且路径长度恒定	✅	→
散列（拉链法）	指针数组 + 同义词链表	否	取决于 $\alpha$：成功 $\approx 1+\frac{\alpha }{2}$	✅ 删除最方便	→
散列（开放定址）	一维数组	否	取决于 $\alpha$，须 $\alpha <1$	⚠️ 删除只能打墓碑	→

表里有三处最容易记错，值得单独拎出来：

第一，有序表的顺序查找，成功 ASL 与无序表完全相同。 有序性只能帮你"提前放弃"，帮不了"提前找到"——第 $i$ 个元素照样要比 $i$ 次。它只改善失败 ASL（从 $n$ 降到约 $\frac{n}{2}$）。

第二，折半查找是全表唯一一个"不支持动态"的。 不是算法不支持插入，而是顺序有序表插入一个元素平均要移动一半元素，$O(n)$ 的维护代价会把 $O(\log n)$ 的查找收益吃干净。

第三，BST 的最坏是 $O(n)$，而 AVL / 红黑树 / B 树的最坏都是对数级。 这正是"为什么需要平衡"的全部答案。

两个"最坏 $O(n)$"，必须能说出触发条件

整章有两处地方会从"很快"直接退化到 $O(n)$，而且都是被反复问的：

🔴 二叉排序树退化：按有序序列依次插入时，每个新结点都挂在最右（或最左），树变成一条单支链，查找退化成顺序查找。

🔴 散列表退化：全部关键字互为同义词时（如 $H(key)=keymod13$ 而关键字都是 13 的倍数），拉链法变成一条长为 $n$ 的链，开放定址法变成一段连续的探测区。

只写结论不写触发条件，等于没掌握。这两条也解释了各自的对策：BST 的对策是引入平衡条件（AVL、红黑树），散列的对策是选一个好的散列函数（$p$ 取质数）并控制装填因子。

失败 ASL 的分母：整章最集中的错误来源

成功 ASL 的分母永远是元素个数 $n$，各方法的差别全在分子上。失败 ASL 的分母则互不相同，只要看一条：数一数有多少个互不等价的失败入口（详见《查找基本概念》）。

查找方法	失败入口是什么	分母
顺序查找（无序表）	只有一种（扫完全表）	不需求平均
顺序查找（有序表）	$n$ 个关键字切出的开区间	$n+1$
折半查找	判定树的外部结点	$n+1$
二叉排序树	BST 的空指针位置	$n+1$
分块查找	由索引查找法与块内查找法共同决定	按定义逐入口数
散列查找	散列函数的值域（能作为查找起点的地址）	值域大小（除留余数法即 $p$）

🔴 散列那一行是唯一的例外，也是最大的失分点：分母是散列函数的模数 $p$，不是表长 $m$，更不是元素个数 $n$。$H(key)=keymod7$ 而表长 11 时，分母是 7。

选型：按四个问题依次收窄

第一问永远是"要不要保持有序"——这一问就把散列表和其余方法分开了。散列表放弃了全序，于是不能范围查询、不能有序输出、不能求前驱后继、不能求最值；反过来说，只要需求里没有这几样，它没有对手。

第二问是"内存还是外存"，因为度量指标会换。 内存里衡量的是比较次数，二路分支就够；外存里衡量的是磁盘 I/O 次数，必须让一次 I/O 读进尽可能多的关键字，于是要多路分支。同一棵 AVL 树放到磁盘上，30 层就是 30 次 I/O，完全不可用——这就是内存用 AVL/红黑树、外存用 B 树的全部理由。

第三问是"静态还是动态"。 这一问的分水岭正好落在折半查找和 BST 之间，而这两者的关系值得说清楚：

折半查找的判定树就是一棵形态最好、由 $n$ 唯一确定的 BST。 差别在于判定树是"算"出来的——不占存储、不可修改；BST 是"存"下来的——占用指针空间、可以插入删除。

第四问才是细分：动态场景里读多写少用 AVL（更平衡、查找略快），写多用红黑树（平衡条件宽松、调整次数少），实现要简单且能接受 $O(\sqrt{n})$ 就用分块查找。

逐场景的选型表（拿不准该选哪个时展开）

场景	选择	判断标准
只需精确匹配，不要有序	散列查找	存储位置与关键字大小无关，天然不支持范围查询；不需要范围查询时它没有对手
频繁插入删除 + 散列	拉链法	开放定址法删除只能打墓碑，墓碑积累会拖垮性能
表长已知、极少删除 + 散列	开放定址法	省掉指针空间
数据在外存 / 数据量极大	B 树 / B+ 树	度量指标从"比较次数"变成"磁盘 I/O 次数"，必须把树高压到个位数
外存 + 大量范围查询	B+ 树	叶结点链表让范围查询降到 $O({\log }_{m}n+k)$
静态 + 表很小	顺序查找	折半的常数开销（算 mid、收缩区间）在小 $n$ 时反而更贵
静态 + 有序 + 顺序存储	折半查找	静态表可以先付一次排序代价，此后每次查找都享受 $O(\log n)$
静态 + 访问概率高度倾斜	顺序查找（按概率降序排列）	$\sum P_i{C}_i$ 可远小于 $\frac{n+1}{2}$，见《顺序查找》
动态 + 内存 + 要最坏可控	AVL / 红黑树	BST 最坏退化成 $O(n)$；平衡结构把最坏也压在 $O(\log n)$
动态 + 读多写少	AVL	比红黑树更"平衡"，查找略快，代价是插删旋转更频繁
动态 + 写多读多	红黑树	平衡条件更宽松，插删的调整次数更少
动态 + 只需一般效率 + 实现要简单	分块查找	$O(\sqrt{n})$ 介于顺序与折半之间，插删只需在块内放/摘一个元素
要在一段文本里找子串	字符串模式匹配	查找对象是子串不是关键字，见《KMP 算法》

各方法 ASL 的来历，以及散列的理论公式表（想知道每个式子怎么推出来的就展开）

查找方法	成功 ASL	失败 ASL	怎么来的
顺序查找（无序）	$\frac{n+1}{2}$	$n$（无监视哨）/ $n+1$（有监视哨）	第 $i$ 个元素比 $i$ 次，$\frac{1}{n}\sum i=\frac{n+1}{2}$
顺序查找（有序）	$\frac{n+1}{2}$	$\frac{n}{2}+\frac{n}{n+1}$	失败分子是 $(1+2+\cdots +n)+n$，最后一段区间只比 $n$ 次
折半查找	$\frac{n+1}{n}{\log }_2(n+1)-1$	$\approx {\log }_2(n+1)$	满二叉判定树 $\frac{1}{n}\sum _{j=1}^{h}j\cdot 2^{j-1}$ 求和
分块查找（顺序索引）	$\frac{b+1}{2}+\frac{s+1}{2}$	逐入口累加	两段查找串联；$s=\sqrt{n}$ 时取最小值 $\sqrt{n}+1$
分块查找（折半索引）	$\approx {\log }_2(\frac{n}{s}+1)+\frac{s}{2}$	逐入口累加	索引段换成折半的平均比较次数
BST 查找	平均 $O({\log }_{2}n)$，最坏 $O(n)$	同量级	比较次数 = 结点层数；树形由插入顺序决定
AVL 查找	$O({\log }_{2}n)$	$O({\log }_{2}n)$	高度受递推 $N_h=N_{h-1}+N_{h-2}+1$ 约束，见《平衡二叉树》
红黑树查找	$O({\log }_{2}n)$	$O({\log }_{2}n)$	树高 $\le 2{\log }_2(n+1)$，见《红黑树》
B 树 / B+ 树	$O({\log }_{\lceil m/2\rceil }n)$ 次 I/O	同量级	树高上下界见《B 树》

散列查找的理论 ASL（设装填因子 $\alpha =\frac{n}{m}$）：

冲突处理方法	查找成功 ASL	查找失败 ASL
线性探测法	$\frac{1}{2}(1+\frac{1}{1-\alpha })$	$\frac{1}{2}(1+\frac{1}{(1-\alpha {)}^2})$
平方探测 / 伪随机探测	$-\frac{1}{\alpha }\ln (1-\alpha )$	$\frac{1}{1-\alpha }$
链地址法（拉链法）	$1+\frac{\alpha }{2}$	$\alpha +e^{-\alpha }$

三条能从公式直接读出的结论：

1. 散列表的 ASL 只与 $\alpha$ 有关，与 $n$ 无关——这就是"接近 $O(1)$"的准确含义，前提是把 $\alpha$ 控制住；
2. 线性探测的失败 ASL 分母是 $(1-\alpha {)}^2$，恶化得最快，这是堆积的量化代价；
3. 拉链法的公式里没有 $\frac{1}{1-\alpha }$，所以 $\alpha \ge 1$ 时仍然有意义，而开放定址法在 $\alpha \to 1$ 时发散。

⚠️ 题目给了具体的表就必须直接计算，不许套这张表的公式——理论公式假设关键字均匀随机分布，与具体一张表通常对不上。

复杂度总表（想一次看全时间/空间量级就展开）

查找方法	平均时间	最坏时间	空间	最坏情形怎么触发
顺序查找	$O(n)$	$O(n)$	$O(1)$	目标在扫描的另一端，或查找失败
折半查找	$O({\log }_{2}n)$	$O({\log }_{2}n)$	$O(1)$（递归实现 $O({\log }_{2}n)$）	目标在判定树最底层
分块查找	$O(\sqrt{n})$（最优块长）	$O(n)$	$O(\sqrt{n})$（索引表）	块长取成 1 或 $n$，退化为顺序查找
BST 查找	$O({\log }_{2}n)$	$O(n)$	$O(n)$	按有序序列依次插入，树退化成单支链
AVL 查找	$O({\log }_{2}n)$	$O({\log }_{2}n)$	$O(n)$	高度被平衡条件压住，无退化情形
红黑树查找	$O({\log }_{2}n)$	$O({\log }_{2}n)$	$O(n)$	同上，最坏树高 $2{\log }_2(n+1)$
B 树 / B+ 树	$O({\log }_{\lceil m/2\rceil }n)$	同左	$O(n)$	每个结点都只有 $\lceil m/2\rceil -1$ 个关键字（半满）
散列查找	$O(1)$（$\alpha$ 受控时）	$O(n)$	$O(m)$ 或 $O(m+n)$	全部关键字互为同义词

考点速记

三条结论：

1. 选型第一问是"要不要保持有序"，这一问把散列表和其余方法分开。
2. 成功 ASL 的分母恒为 $n$；失败 ASL 的分母是失败入口数——比较类是 $n+1$，散列是散列函数的值域大小。
3. 两个"最坏 $O(n)$"要能说出触发条件：BST 按有序序列插入；散列全部关键字同义。

这一节在真题里被考过的形式（下方「真题练习」与《查找基本概念》共用同一批题，是整章的"分析类"题目）：

• 不等概率下重排元素求更短的 ASL（大题）：给 4 个元素与不等的查找概率，已知折半查找 ASL 为 2.2，要求分别在顺序存储与链式存储下给出更优方案。两问的答案都是按概率递减排列 + 顺序查找（ASL = 2.1）。链式那一问的额外考点是：链表上根本用不了折半，所以顺序查找是唯一选择。
• 影响散列查找 ASL 的因素：装填因子、散列函数、冲突解决策略——三个全都影响。
• 提高散列表查找效率的措施：设计冲突少的散列函数 ✓、避免堆积 ✓、增大装填因子 ✗。
• 堆积现象直接影响什么：答平均查找长度。
• 各类查找的 ASL 计算：散列的成功/失败 ASL、分块查找的最优块长，分别落在开放定址法、分块查找那几篇。

易错：时间复杂度相同不等于性能相同。 B 树与 AVL 都是对数级，但外存场景下底数（扇出）和常数（一次 I/O 的代价）才是决定性的。

易错：散列失败 ASL 的分母与其余方法完全不同。 比较类查找是 $n+1$，散列是散列函数的值域大小。

易错：折半查找"不支持动态"的理由是维护代价，不是算法限制。 答"折半查找算法不能插入"是不准确的。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）7.5 节「小结」，p229： 按线性表、树表、散列表三类组织查找表的总纲； 表 7.5「顺序查找、折半查找和分块查找的比较」给出三者在时间复杂度、查找特点、 适用情况三个维度的对照——顺序查找"算法简单，对表结构无任何要求，但查找效率较低"， 适用于"任何结构的线性表，不经常做插入和删除"；折半查找"对表结构要求较高， 查找效率较高"，适用于"有序的顺序表，不经常做插入和删除"； 分块查找"效率介于折半查找和顺序查找之间"，适用于"块间有序、块内无序的顺序表， 经常做插入和删除"。
• 同页表 7.6「折半查找和二叉排序树查找的比较」：两者时间复杂度同为 $O({\log }_{2}n)$， 但折半查找"数据结构采用有序的顺序表，插入和删除操作需移动大量元素"， 适用于"不经常做插入和删除的静态查找表"；二叉排序树查找"插入和删除操作无需移动元素， 只需修改指针"，适用于"经常做插入和删除的动态查找表"。
• 同页还给出：二叉排序树"在形态均匀时性能最好，而形态为单支树时其查找性能则退化为 与顺序查找相同"；B- 树"是一种在外存文件系统中常用的动态索引技术"； 以及散列表"不是以关键字比较为基础进行查找的……不仅平均查找长度和记录总数无关， 而且可以通过调节装填因子，把平均查找长度控制在所需的范围内"。
• 同书 p227 表 7.3：四种冲突处理方法在等概率下的理论平均查找长度。

相关知识

查找基本概念（ASL 与判定树两件工具，本篇所有结论由那里推出）｜ 顺序查找、折半查找、分块查找（线性表路线）｜ 二叉排序树、平衡二叉树、红黑树（树表路线的内存版本，对应六（五），原理在树那一章）｜ B 树、B+ 树（树表路线的外存版本）｜ 拉链法、开放定址法（散列路线）｜ 串的基本概念、BF 算法、KMP 算法、全文检索（六（八）字符串模式匹配）｜ 排序算法对比｜外部排序

相关文章

• 查找基本概念
• 顺序查找
• 折半查找（二分查找）
• 分块查找
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B 树
• B+ 树
• 哈希表：拉链法
• 哈希表：开放定址法

交互体验

前往完整可视化页面 →

真题练习

相关真题（7题）

2025Q72分2023Q92分2022Q92分2019Q82分2018Q92分2014Q82分2013Q4210分