Searching algorithms

欢迎来到搜索算法的世界！

你好！在这一章中，我们将深入探讨计算机科学家必备的一项基础技能：如何快速查找信息。无论是在大型数据库中进行检索，还是在手机通讯录里查找联系人，算法都在背后默默发挥着作用。

我们将探索两种主要的搜索算法：直观但速度较慢的线性搜索 (Linear Search)，以及精妙但有前提条件的二分搜索 (Binary Search)。理解这些算法将帮助你编写出更高效、更智能的程序。别担心，如果刚开始觉得有些复杂，我们会用大量的类比来帮你拆解这些概念！

3.4.1 搜索算法

1. 线性搜索算法（慢但稳妥的方法）

线性搜索（也称顺序搜索）是在列表或数组中查找目标元素最简单的方法。正如其名，它的执行方式非常直接：从列表的开头开始，按直线顺序一个接一个地检查，直到找到目标元素为止。

线性搜索的工作原理（分步说明）

想象你面前有一排没有标记的储物柜，而你要寻找的是“42号储物柜”。你从第一个柜子开始，逐个检查，直到找到42号为止。

1. 从列表的最开始（索引 0）出发。
2. 查看当前的元素。
3. 当前的元素是你正在寻找的目标吗？
   • 如果是是，停止搜索并返回该位置（索引）。任务完成！
   • 如果是否，移动到列表中的下一个元素。
4. 如果你到达了列表末尾仍未找到，则说明该元素不在列表中。

线性搜索的关键特性

• 无需排序： 列表不需要预先排序。这是一个巨大的优势！
• 实现难度： 该算法代码编写简单，通常使用一个简单的循环（迭代）即可实现。
• 效率（时间复杂度）： 在最坏的情况下，你必须检查列表中的每一个元素。如果列表有 $N$ 个元素，你最多可能需要执行 $N$ 次检查。这被称为 $O(n)$ 效率（线性时间）。

你知道吗？（效率技巧）

虽然线性搜索的基础版本会检查所有元素，但高效的版本会一旦找到目标就立即停止。如果目标正好是第一个元素，搜索瞬间即可完成！如果目标是最后一个元素，或者根本不存在，则搜索耗时最长。

2. 二分搜索算法（快速但挑剔的方法）

二分搜索算法极其迅速，但它有一个至关重要的前提规则：列表或数组必须是有序的。如果数据没有经过排序（例如数字或字母顺序），二分搜索将无法正常工作。

二分搜索使用了一种强大的策略，叫做分治法 (Divide and Conquer)。它不是一次检查一个元素，而是通过每一步操作排除掉剩下数据中的一半。

类比：查字典

想象一下你在查阅一本厚厚的纸质字典（它当然是按字母顺序排列的！）。

你肯定不会从第1页开始翻。你会大约从中间位置打开。如果你要找的单词以“S”开头，而中间那一页是“K”，你就能立刻排除掉字典的前半部分！然后，你在剩下的一半中重复这个过程，不断将搜索范围减半。

二分搜索的工作原理（分步说明）

我们通过三个指针来追踪搜索范围：低位 (Low)、高位 (High) 和 中位 (Mid)。

1. 确保列表是有序的。
2. 将 Low 指针指向列表开头（索引 0）。
3. 将 High 指针指向列表结尾（索引 $N-1$）。
4. 当 Low 小于或等于 High 时：
   1. 计算 Mid 点：$Mid = (Low + High) / 2$（向下取整）。
   2. 将 Mid 处的元素与 目标值 (Target) 进行比较：
   • 如果 $List[Mid] = Target$：成功！返回 Mid。
   • 如果 $List[Mid] < Target$：目标一定在后半部分。移动 Low 指针：$Low = Mid + 1$。
   • 如果 $List[Mid] > Target$：目标一定在前半部分。移动 High 指针：$High = Mid - 1$。
5. 如果循环结束仍未找到，则说明该元素不在列表中。

追踪示例

在列表中搜索目标值 45：[10, 20, 30, 40, 45, 50, 60, 70]（8个元素）

第1轮：

• Low = 0, High = 7
• Mid = (0 + 7) / 2 = 3。$List[3]$ 为 40。
• 45 > 40。目标值更大。排除掉前半部分。
• 新的 Low = $Mid + 1 = 4$。（新范围：[45, 50, 60, 70]）

第2轮：

• Low = 4, High = 7
• Mid = (4 + 7) / 2 = 5。$List[5]$ 为 50。
• 45 < 50。目标值更小。排除掉后半部分。
• 新的 High = $Mid - 1 = 4$。（新范围：[45]）

第3轮：

• Low = 4, High = 4
• Mid = (4 + 4) / 2 = 4。$List[4]$ 为 45。
• 45 = 45。找到了！

仅仅用了3次检查就找到了目标！而线性搜索则需要5次检查。

二分搜索的效率

就时间而言，二分搜索极其高效。每一次比较都将搜索空间减半。对于 $N$ 个元素的列表，最大检查次数与 $N$ 的对数成正比。这被写作 $O(\log n)$。

示例： 如果你有100万个元素 ($N=1,000,000$)，线性搜索可能需要100万次检查。而二分搜索最多只需20次！

3. 搜索算法对比

在选择算法时，我们主要从两个维度进行比较：效率（运行速度）和 条件（数据所需的状态）。

对比表

特性	线性搜索	二分搜索
前提条件	列表可以是无序的。	列表必须是有序的。
时间效率（最坏情况）	$O(n)$（线性时间）	$O(\log n)$（对数时间）
操作方式	按顺序逐个检查元素。	反复排除一半的数据。
适用场景	小型列表，或频繁变动且难以保持排序的列表。	超大型、相对稳定且已排序的数据集（如数据库）。

理解时间效率

在 AS 级别，你需要能够对比时间效率，而不必仅仅依赖大 O 记号法。

• 线性搜索： 如果你将列表大小增加一倍（从10个元素增至20个），搜索时间大约增加一倍。搜索时间与列表大小呈线性增长关系。
• 二分搜索： 如果你将列表大小增加一倍，搜索时间仅增加一个步骤（多执行一次减半操作）。随着列表大小增长，其所需时间增长得极其缓慢。

结论： 对于大型数据集，虽然排序（如果列表尚未排序）需要初始时间成本，但通常是值得的，因为二分搜索比线性搜索快得多。