# 标准查找算法

> 计算机科学 · CIE A-Level 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u9-standard-searching-algorithms/

本模块讲解CIE A-Level 9618要求的两种标准查找算法：顺序（线性）查找和二分查找。你将学习它们的工作原理、复杂度，以及在考试题目中何时使用哪一种。

**先修:** [基础算法伪代码规范](https://www.owlsprep.com/zh/study/cie-9618-u8-pseudocode-conventions/); [算法复杂度的大O表示法](https://www.owlsprep.com/zh/study/cie-9618-u9-time-space-complexity/)

## 学习目标

- 区分顺序查找和二分查找算法
- 为有序和无序数据正确实现顺序查找与二分查找
- 比较标准查找算法的时间和空间复杂度
- 在给定考试题目场景中判断哪一种查找算法更合适

## 顺序（线性）查找

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

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

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

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

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

> **tip**
>
> 请记住，顺序查找可以用于无序数据。如果你的数据未排序，不需要预处理就能使用的标准查找算法只有顺序查找。

## 二分查找

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

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

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

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

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

> **warning**
>
> 二分查找仅适用于有序数据集。如果数据集未排序，你必须先对其排序，这会为整个过程增加$O(n \log n)$的时间开销。

## 复杂度与算法选择

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

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

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

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

**考试命令词**

本考点常见的考试指令术语有以下特定要求：

- **Distinguish** — 说明两种算法之间的关键区别，通常需要比较复杂度、适用场景等性质 *(Distinguish between linear and binary search)*

- **Write pseudocode** — 使用CIE标准伪代码规范编写可运行的算法，包含所有循环和条件判断 *(Write pseudocode for an iterative binary search)*

## 常见错误

- **错误做法:** 对无序数据集使用二分查找
  - 原因: 二分查找依赖有序性来排除一半搜索空间，在无序数据中它通常无法找到已经存在的目标
  - 正确做法: 无序数据使用顺序查找，或先对数据排序再使用二分查找
- **错误做法:** 二分查找边界计算出现偏移1错误
  - 原因: 错误设置low/high边界（例如将low设为mid而非low = mid + 1）会导致无限循环或遗漏目标
  - 正确做法: 比较后始终更新边界排除中点，因为中点已经检查过了
- **错误做法:** 声称二分查找的运行速度总是比顺序查找快
  - 原因: 对于小规模数据集，二分查找边界计算的开销可能比简单顺序扫描更大
  - 正确做法: 说明二分查找对于大规模数据集是渐近更快的，但对于小输入规模不一定更快
- **错误做法:** 认为顺序查找的空间复杂度总是$O(1)$
  - 原因: 递归实现的顺序查找调用栈会占用$O(n)$栈空间，不是常数空间
  - 正确做法: 被问到空间复杂度时，需要说明实现是迭代（$O(1)$）还是递归（$O(n)$）

## 速查表

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

## 下一步

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

- [标准排序算法](https://www.owlsprep.com/zh/study/cie-9618-u9-standard-sorting-algorithms/)
- [算法跟踪](https://www.owlsprep.com/zh/study/cie-9618-u9-algorithm-tracing/)
- [数据类型与结构](https://www.owlsprep.com/zh/study/cie-9618-u10-overview/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u9-standard-searching-algorithms/