标准查找算法

计算机科学· 第9单元：算法设计与问题求解· 20 分钟阅读

1. 顺序（线性）查找★★☆☆☆⏱ 6 min

📘 定义

顺序查找

一种暴力顺序查找算法，按顺序遍历数据集中的每个元素，将每个元素与目标值比较，直到找到匹配项或到达数据集末尾。可同时用于有序和无序数据集。

例:

在未排序的学号列表中查找某个特定姓名。

顺序查找是最简单的查找算法，不需要对输入数据集进行预处理。它可以在任何顺序存储结构上实现，包括数组、链表和无序线性集合。

📐 例题

使用顺序查找在数组[8, 3, 17, 5, 12]中查找目标值17，逐步演示算法过程。

1
1. 从第一个元素（索引0，值为8）开始，将其与目标17比较。
2
1. $8 \neq = 17$ ，移动到下一个元素（索引1，值为3）。
3
1. $3 \neq = 17$ ，移动到下一个元素（索引2，值为17）。
4
1. 17匹配目标，返回索引2作为结果。

2. 二分查找★★★☆☆⏱ 8 min

📘 定义

二分查找

一种分治查找算法，每次将有序搜索空间减半，每轮迭代可减少一半需要检查的元素数量。仅适用于预先排序的数据集。

例:

在排序好的纸质词典中查找某个特定单词。

二分查找利用输入的有序性质，每次比较后可以排除一半的搜索空间。它可以通过迭代或递归两种方式实现。

📐 例题

使用二分查找在有序数组[3, 7, 12, 15, 21, 27, 32]中查找目标21，逐步演示过程。

1
1. 初始化 low = 0（起始索引），high = 6（数组的结束索引）
2
1. 第一轮迭代：计算中点 = $\frac{0 + 6}{2} = 3$ ，中点位置的值为15。
3
1. 比较得 $15 < 21$ ：排除左半部分，设置 low = mid + 1 = 4。
4
1. 第二轮迭代：中点 = $\frac{4 + 6}{2} = 5$ ，中点位置的值为27。
5
1. 比较得 $27 > 21$ ：排除右半部分，设置 high = mid - 1 = 4。
6
1. 第三轮迭代：中点 = $\frac{4 + 4}{2} = 4$ ，中点位置的值为21，与目标匹配。返回索引4。

3. 复杂度与算法选择★★★☆☆⏱ 6 min

在CIE考试中，题目经常要求你比较两种算法、说明它们的时间和空间复杂度，并为给定场景选择合适的算法。

性质	顺序查找	二分查找
支持无序数据	是	否
需要预先排序	否	是
最坏情况时间复杂度	$O (n)$	$O (lo g n)$
最好情况时间复杂度	$O (1)$	$O (1)$
平均情况时间复杂度	$O (n)$	$O (lo g n)$
空间复杂度（迭代实现）	$O (1)$	$O (1)$
空间复杂度（递归实现）	$O (n)$	$O (lo g n)$

📐 例题

某学校存储了1000条未排序的学生记录，查找学生ID应该使用哪一种查找算法？说明你的理由。

1
1. 确认数据集性质：题目明确说明记录是未排序的。
2
1. 二分查找只能用于有序数据，不先排序就无法使用。
3
1. 对1000条记录排序会增加不必要的额外处理时间。
4
结论：该场景下顺序查找是合适的选择。

4. 常见陷阱

错误做法:

对无序数据集使用二分查找

原因:

二分查找依赖有序性来排除一半搜索空间，在无序数据中它通常无法找到已经存在的目标

正确做法:

无序数据使用顺序查找，或先对数据排序再使用二分查找

错误做法:

二分查找边界计算出现偏移1错误

原因:

错误设置low/high边界（例如将low设为mid而非low = mid + 1）会导致无限循环或遗漏目标

正确做法:

比较后始终更新边界排除中点，因为中点已经检查过了

错误做法:

声称二分查找的运行速度总是比顺序查找快

原因:

对于小规模数据集，二分查找边界计算的开销可能比简单顺序扫描更大

正确做法:

说明二分查找对于大规模数据集是渐近更快的，但对于小输入规模不一定更快

错误做法:

认为顺序查找的空间复杂度总是 $O (1)$

原因:

递归实现的顺序查找调用栈会占用 $O (n)$ 栈空间，不是常数空间

正确做法:

被问到空间复杂度时，需要说明实现是迭代（ $O (1)$ ）还是递归（ $O (n)$ ）

5. 速查表

算法	前提条件	最坏时间	最佳适用场景
顺序查找	无	$O (n)$	小规模/无序数据集
迭代二分查找	有序数据	$O (lo g n)$	大规模有序数据集
递归二分查找	有序数据	$O (lo g n)$	递归问题求解

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 12
比较顺序查找和二分查找
2023 · 11
编写二分查找的伪代码
2024 · 13
说明两种查找算法的复杂度

深入阅读

syllabusCIE 9618 Official Syllabus查看最新大纲更新

下一步

标准查找算法是本单元后续更复杂算法问题的基础构件。查找是许多高级算法的核心组件，包括排序算法、图遍历和数据库查询处理。掌握顺序查找和二分查找的区别有助于你正确回答试卷1和试卷2中的问题求解题目，考试中经常要求你直接编写伪代码或跟踪这些算法的执行过程。接下来你可以学习标准排序算法，考试中查找和排序经常结合出题。