欢迎来到搜索算法的世界！
你好，未来的计算机科学家们！本章将带你深入了解计算机是如何高效查找信息的。想一想，你每天搜索多少次信息——手机里的联系人、Spotify 上的歌曲，或是用搜索引擎查询某个事实。快速查找数据是计算机最基础的工作之一！
在这一节中，我们将探索计算机在数据列表中进行搜索的两种核心方法：线性搜索 (Linear Search) 和 二分搜索 (Binary Search)。理解这些算法对于构建快速、有效的程序至关重要。让我们开始吧！
1. 什么是搜索算法？
搜索算法 (Searching Algorithm) 是一种分步执行的过程，用于从存储数据的任何数据结构中检索元素（或项）。其目标很简单：尽可能快地找到目标项，或者确定该项不存在。
- 数据集 (Data Set) 或列表 (List)： 这是计算机进行搜索的一系列项目（例如：名单、价格列表或数字序列）。
- 目标项 (Target Item)： 你正在寻找的具体项目。
2. 线性搜索 (顺序搜索)
什么是线性搜索？
线性搜索 (Linear Search)，有时也称为 顺序搜索 (Sequential Search)，是最简单的方法。它的工作原理是从头到尾逐个检查列表中的每一项。
类比：想象你有一堆 100 张未排序的 CD，你想找其中一张特定的专辑。你从最上面开始，检查第一张 CD 的标签，然后是第二张、第三张，依此类推，直到找到它（或者检查完那一堆的所有 CD）。
线性搜索的工作原理（分步演示）
- 从列表的第一个元素开始。
- 将当前元素与目标项进行比较。
- 如果匹配：说明找到了！搜索立即停止。
- 如果不匹配：移动到列表中的下一个元素。
- 重复步骤 2–4，直到找到目标或到达列表末尾。
- 如果到达末尾仍未找到，则说明该项不在列表中。
示例：在列表中搜索数字 55。
列表：[10, 80, 25, 55, 40]
目标：55
步骤 1：10 等于 55 吗？不是。（移至下一项）
步骤 2：80 等于 55 吗？不是。（移至下一项）
步骤 3：25 等于 55 吗？不是。（移至下一项）
步骤 4：55 等于 55 吗？是的！找到目标！
线性搜索的关键特征
- 数据顺序要求： 它适用于未排序的列表（数据可以以任何随机顺序排列）。这是它最大的优势！
- 效率（速度）： 在最坏的情况下（如果目标项是最后一个，或者根本不存在），计算机必须检查列表中的每一项。对于非常大的列表，这可能会很慢。
快速回顾：线性搜索
线性搜索可靠且简单，无论列表是否排序都能工作。然而，对于长列表来说，它效率很低（很慢），因为它从不跳过任何元素。
3. 二分搜索
如果一开始觉得这有点复杂，别担心——其实它基于你每天可能已经在用的某种方法！二分搜索比线性搜索快得多，但它有一个至关重要的前提要求。
关键前提：排序数据
二分搜索 (Binary Search) 算法仅在数据集已排序（按字母或数字顺序排列）的情况下有效。如果数据没有排序，你就不能使用这种方法！
类比：试想一下在字典中查找单词或在电话簿中查找号码。这些书都是按字母顺序排列的。如果不是这样，你就必须使用线性搜索（检查每一页！）。
二分搜索的工作原理（“折半”法）
二分搜索使用“分而治之”的方法。它不是一次检查一项，而是检查中间项，并立即排除掉剩余列表的一半。
二分搜索的工作原理（分步演示）
- 找到列表的中间元素。
- 将中间元素与目标项进行比较。
-
三种可能的结果：
- 匹配： 如果中间项等于目标项，搜索完成。
- 目标较小： 如果目标项比中间项小，则目标一定在列表的左半部分（因为列表已排序）。你可以安全地丢弃整个右半部分。
- 目标较大： 如果目标项比中间项大，则目标一定在列表的右半部分。你可以安全地丢弃整个左半部分。
- 在剩余的（较小的）列表半部分重复步骤 1–3，直到找到目标或剩余列表为空。
示例：在排序列表中搜索数字 17。
列表：[3, 7, 10, 12, 15, 17, 20, 22, 25]
目标：17
步骤 1（第一次搜索）：
列表共有 9 个项目。中间项是第 5 个：15。
15 等于 17 吗？不是。
17 比 15 大还是小？大。
操作：丢弃 15 及其左侧的所有数字（3, 7, 10, 12）。
步骤 2（第二次搜索）：
剩余列表：[17, 20, 22, 25]
新的中间项在 20 和 22 之间。我们选 20。
20 等于 17 吗？不是。
17 比 20 大还是小？小。
操作：丢弃 20 及其右侧的所有数字（22, 25）。
步骤 3（第三次搜索）：
剩余列表：[17]
中间项是 17。
17 等于 17 吗？是的！找到目标！
请注意，我们只用了 3 步就找到了目标，尽管列表有 9 个项目！线性搜索可能需要 6 步。对于 100 万个项目的列表，二分搜索的速度会快得多。
记忆小贴士：二分搜索
记住单词 "Binary" 意为“二”。二分搜索总是将问题分成两个半部分并丢弃其中一半。
要避免的常见错误： 同学们经常忘记 二分搜索要求列表必须先排序！
4. 比较线性搜索与二分搜索
计算机应该何时使用哪种方法呢？这完全取决于列表是否已排序以及列表的大小。
主要区别与效率
效率 (Efficiency) 指的是算法运行的速度，特别是在数据列表规模增长时。
线性搜索：
- 适用于： 未排序或已排序的数据。
- 效率： 低（慢）。在最坏情况下，如果列表有 N 个项目，它最多需要 N 步。
- 何时使用： 当列表较小，或者数据未排序且你没有时间先进行排序时。
二分搜索：
- 适用于： 仅限已排序的数据。
- 效率： 高（非常快）。每一步都将剩余数据减半，意味着它所需的步数远少于列表的规模。
- 何时使用： 当列表非常大且数据已经排序（或者值得花费时间先进行排序）时。
你知道吗？如果你有一个 1,000,000 个项目的列表，线性搜索可能需要 1,000,000 次检查。而二分搜索只需大约 20 次！这可是巨大的速度差异！
总结表：选择合适的搜索算法
| 特性 | 线性搜索 | 二分搜索 | |---|---|---| | 数据要求 | 未排序或已排序 | 必须已排序 | | 最坏情况速度 | 慢（检查每一项） | 非常快（每次减半） | | 实现难度 | 编码简单 | 编码较复杂 |
最终核心要点：搜索算法
如果你需要在大型、已排序的列表中进行搜索，二分搜索是速度冠军。如果你的列表很小，或者数据杂乱且未排序，线性搜索是唯一能保证你找到目标的选项。