欢迎来到搜索算法的世界！
在计算机科学中，搜索是最基础的运算之一。无论你是在手机通讯录寻找联系人、在 YouTube 上找特定视频，还是在数据库中寻找最高分数，背后都有算法在帮你找出这些数据。在本章中，我们将探讨计算机寻找目标的两种主要方式：线性搜索 (Linear Search) 与 二分搜索 (Binary Search)。
如果一开始觉得“算法”听起来很深奥，别担心！读完这些笔记后，你会发现它们其实就像我们日常生活中解决问题的方法一样直观。
1. 线性搜索：逐一比对法
线性搜索是最简单的搜索方式。它会从列表的开头开始，逐一检查每一个项目，直到找到目标或是到达列表的尽头为止。
运作流程（步骤教学）：
1. 从列表中的第一个项目开始。
2. 将该项目与你要找的目标（target）进行比较。
3. 如果两者相符，停止！你已经找到了。
4. 如果不相符，移动到下一个项目。
5. 重复步骤 2-4，直到找到项目或检查完整个列表。
现实生活中的比喻：
想象你在凌乱的洗衣篮中找一件特定的衬衫。你拿起第一件衬衫，检查一下，放到旁边；再拿起第二件，检查一下，以此类推。这就是线性搜索的运作方式！
效率小贴士：
课程大纲提到了这种搜索的两个版本：
- 低效版本：算法即使已经找到目标，仍会继续检查剩余的每一个项目。
- 进阶版本：算法在找到项目后立即停止。这能节省不少时间！
快速回顾：线性搜索适用于任何列表，无论该列表是已排序（有顺序）还是未排序（随机）。
重点总结：线性搜索虽然简单，但在数据量庞大时效率较低，因为在最坏的情况下，你必须检查每一个项目。
2. 二分搜索：“分而治之”法
二分搜索比线性搜索快得多，但它有一个非常重要的规则：列表必须已经排序（例如：按字母顺序排列，或由小到大排列数字）。
运作流程（步骤教学）：
1. 找出列表的中间项目。
2. 将中间项目与你的目标进行比较。
3. 如果中间项目就是目标，恭喜你完成了！
4. 如果你的目标比中间项目小，就舍弃列表的右半部分。
5. 如果你的目标比中间项目大，就舍弃列表的左半部分。
6. 重复上述过程，处理剩余的部分，直到找到该项目为止。
寻找中间点的数学运算：
要找出中间的索引值（index），我们通常会使用这个简单的公式：
\( \text{mid} = \text{integer}(\frac{\text{first\_index} + \text{last\_index}}{2}) \)
现实生活中的比喻：
试想在印刷版的字典里找一个词。你不会从第 1 页开始读每一个词（那是线性搜索）。相反地，你会直接翻开中间。如果你想找的词在中间页的“前面”，你会忽略整本书的后半部分，只在前半部分继续寻找。
你知道吗？二分搜索非常迅速，即使你面对的是一个拥有 100 万个项目的列表，最多也只需要 20 个步骤就能找到你的目标！
重点总结：二分搜索对于处理大量数据极为有效，但前提是数据必须已经排序。
3. 两种算法的比较
在考试中，你可能会被要求比较这两种算法。以下是一个简单的对照表，帮助你记住它们的差异：
线性搜索 (Linear Search)
- 必要条件：无。适用于已排序或未排序的列表。
- 时间效率：对于大型列表较慢。时间消耗随着项目数量线性增长。
- 最佳使用场景：列表很短，或者数据完全未经排序时。
二分搜索 (Binary Search)
- 必要条件：数据必须先经过排序。
- 时间效率：非常快。即使列表的大小加倍，也只需要多花一个步骤就能完成搜索。
- 最佳使用场景：当你拥有一个庞大且已排序的数据集时。
常见的考试陷阱：在考试题目中，千万不要试图对“未排序的列表”使用二分搜索。你必须先声明该列表需要先进行排序！
记忆技巧与诀窍
- Linear（线性）= Line（队列）。想象一排人，你要一个一个地检查他们。
- Binary（二分）= Bi（二）。想象一辆有两个轮子的脚踏车（Bicycle），你总是将列表分成两半。
总结检查清单
- 你能根据一串数字进行线性搜索的推演吗？
- 你知道高效的线性搜索在找到项目后会停止吗？
- 你能解释为什么二分搜索必须在已排序的列表上执行吗？
- 你能在二分搜索的步骤中计算列表的中间点吗？
- 你能解释对于 10,000 个已排序的名字列表，哪种算法更快吗？（提示：是二分搜索！）
继续练习！尝试画出一些数字列表，并用笔模拟算法的操作过程。你很快就会成为高手！