欢迎来到搜索算法的世界！
你有没有试过在庞大的播放列表中寻找一首特定的歌曲，或者在电话簿中找某一个名字？如果有，那你其实已经执行过一次搜索（Search）了！在计算机科学中，搜索就是从数据集合（如列表或数组）中找出特定数据的过程。
不用担心“算法”听起来很吓人——它们其实就只是一组用来完成任务的“指令集”。今天，我们要来看看计算机寻找目标时最主要的两种方式：线性搜索（Linear Search）和二分搜索（Binary Search）。
1. 线性搜索：逐一检查法
线性搜索是最简单的搜索方法。它会从列表的最开头开始，逐一检查每一个项目，直到找到目标或检查完所有项目为止。
运作原理（机制）：
想象你面前有一排五个封闭的盒子，你要寻找里面隐藏的金币。
1. 打开第一个盒子。里面有金币吗？如果有，停止！如果没有，继续下一个。
2. 打开第二个盒子。里面有金币吗？如果没有，继续下一个。
3. 依此类推，持续检查第三、第四和第五个盒子，直到找到金币或盒子全数打开为止。
现实生活中的例子：
在凌乱、未整理的抽屉里找一双特定的袜子。你必须一只一只地把袜子拿出来看，直到找到正确的那一双为止。
快速重温：线性搜索的优缺点
优点：
• 非常容易理解和编写程序。
• 适用于任何列表，无论项目是有序排列（已排序）还是完全混乱（未排序）。
缺点：
• 对于大型列表来说，它非常慢。如果你有 1,000,000 个项目，而你要找的那个刚好在最后面，计算机就必须进行 1,000,000 次检查！
重点提醒： 当列表很小，或者列表没有经过排序时，使用线性搜索最合适。
2. 二分搜索：分治法（Divide and Conquer）
二分搜索快得多，但它有一个非常重要的前提规则：列表必须是已排序的（例如：按字母顺序排列，或是由小到大的数字排列）。
运作原理（机制）：
二分搜索不是从开头开始，而是直接跳到列表的中间。
1. 查看已排序列表的中间项目。
2. 这是你要找的项目吗？如果是，那就完成了！
3. 你的目标比中间项目小吗？如果是，就舍弃列表的右半部分。
4. 你的目标比中间项目大吗？如果是，就舍弃列表的左半部分。
5. 对剩下那一半重复此过程，直到找到目标为止。
你知道吗？
二分搜索的效率高得惊人。即使你要在全世界所有人（约 80 亿人）的名录中进行搜索，二分搜索也只需约 33 个步骤就能找到特定名字！
现实生活中的例子：
想象一下在字典里找一个词。你不会从第 1 页开始翻，你会从中间打开。如果目标词汇在当前页面之后，你就忽略字典的前半部分，只在后半部分搜索。
快速重温：二分搜索的优缺点
优点：
• 对于大量数据来说，速度极快。
• 每进行一次检查，你就能删除剩余数据中一半的范围。
缺点：
• 它只适用于已经排序过的列表。如果列表很杂乱，算法就会失效。
重点提醒： 二分搜索是处理大数据集的“速度之王”，但你必须先将列表排序！
3. 两者比较：哪一个更好？
在考试中，你可能会被要求比较这两种方法。这里有一份实用的指南帮助你选择：
1. 列表是否需要已排序？
• 线性搜索：不需要。
• 二分搜索：需要。
2. 速度如何？
• 线性搜索：慢（特别是对于长列表）。
• 二分搜索：快（特别是对于长列表）。
3. 我应该在什么时候使用？
• 线性搜索：当列表很小或未排序时。
• 二分搜索：当列表很大且已经排好序时。
记忆小技巧：“线性”法
要记住线性搜索（Linear Search），想象排成一线（Line）的人群。为了找到某个人，你必须沿着队伍走，逐一检查每一个人。
应避免的常见错误
• 错误： 以为二分搜索适用于任何列表。
修正：在建议使用二分搜索之前，务必先检查列表是否已排序！
• 错误： 认为线性搜索因为比较慢所以很“糟糕”。
修正：如果列表非常小，或者数据变动太频繁，以至于排序所需的成本过高，那么线性搜索其实是更好的选择。
快速复习测验（心智检查！）
1. 哪种搜索算法会从第一个项目开始？（答案：线性搜索）
2. 在使用二分搜索之前，列表必须具备什么条件？（答案：必须是已排序的）
3. 如果你有一个包含 10 个项目的列表，哪种搜索方式比较简单？（答案：线性搜索）
4. 如果你在 1,000,000 个已排序的项目中进行搜索，哪种方法比较快？（答案：二分搜索）
如果起初觉得这些概念有点难懂也别担心！只要记住：线性 =“逐一搜索”，二分 =“对半分割”。你一定行的！