欢迎来到搜索算法的世界！
你好！在这一章节中，我们将探讨计算机如何在庞大的数据集内找到特定信息。无论你是要在手机中搜索联系人，还是在 Google 上寻找网页，背后都有搜索算法在运作。针对 AQA A Level 课程，我们需要掌握三种主要方法：线性搜索 (Linear Search)、二分搜索 (Binary Search) 和 二叉树搜索 (Binary Tree Search)。别担心这些名词看起来很复杂，我们会一步一步为你拆解！
1. 线性搜索：逐一检查法
线性搜索是找到目标最简单的方法。想象你有一堆混乱的袜子，正在寻找那只有圆点图案的。你会拿起第一只检查，看过后放下，再拿起第二只，以此类推，直到找到正确的那一只为止。
运作原理（步骤说明）：
1. 从列表的最开头（索引 0）开始。
2. 将当前的项目与你要搜索的目标进行比较。
3. 如果两者相符，恭喜！你找到了。
4. 如果不符，移动到列表中的下一个项目。
5. 重复以上步骤，直到找到目标或检查完列表中的所有项目。
复杂度与效率
在计算机科学中，我们使用 Big O 符号 (Big O notation) 来描述算法的快慢。线性搜索的时间复杂度为 \(O(n)\)。
为什么呢？ 因为在最坏的情况下（即目标项目位于列表末尾，甚至根本不在列表中），你必须检查列表中的每一个项目（共 \(n\) 个）。
小贴士：线性搜索是此处唯一适用于未排序数据的算法。如果你的列表完全没有整理过，线性搜索就是你唯一的选择！
重点总结：
线性搜索编写代码简单，但对于大量数据来说效率较慢。其时间复杂度为 \(O(n)\)。
2. 二分搜索：分治法
二分搜索的速度要快得多，但它有一个非常重要的规则：数据必须已经过排序（例如按字母顺序或数字大小排列）。如果列表未经排序，二分搜索将无法运作！
比喻： 想象你在实体字典中查单词。你不会从第 1 页开始翻，而是打开中间，看看你要找的字是在那一页之前还是之后，然后直接舍弃掉那一半你不需要的部分。
运作原理（步骤说明）：
1. 找到列表的中间元素。
2. 将中间元素与你的目标进行比较。
3. 如果目标等于中间元素，你就完成了！
4. 如果目标小于中间元素，舍弃列表的右半部分。
5. 如果目标大于中间元素，舍弃列表的左半部分。
6. 对剩余的部分重复此过程，直到找到目标为止。
复杂度与效率
由于你每次都在减半搜索范围，这个算法的速度非常快。其时间复杂度为 \(O(\log n)\)。
常见错误： 忘记列表必须先排序。在考试中，如果题目要求你对一个未排序的列表执行二分搜索，你的第一步必须先说明需要先对列表进行排序！
重点总结：
二分搜索对于大型数据集非常有效，但前提是数据必须已排序。其时间复杂度为 \(O(\log n)\)。
3. 二叉树搜索
二叉树搜索涉及在二叉搜索树 (BST) 中进行搜索。在这种结构中，每个“节点 (node)”都有一个值，并且最多可以有两个“子节点”（左和右）。
BST 的黄金法则：
对于树中的任何节点：
- 小于该节点的值会放在左边。
- 大于该节点的值会放在右边。
记忆法： Left is Less！（左边就是比较小的！）
如何搜索二叉树（步骤说明）：
1. 从根节点 (Root)（最顶端的节点）开始。
2. 根节点是你想要的值吗？如果是，停止！
3. 你的目标是否小于当前节点？如果是，移动到左侧子节点。
4. 你的目标是否大于当前节点？如果是，移动到右侧子节点。
5. 重复上述步骤，直到找到目标值，或者遇到“null”（空值），这意味着该值不在树中。
复杂度与效率
就像二分搜索一样，如果树是平衡的，你本质上是在每一步将需要检查的节点数量减半。因此，时间复杂度为 \(O(\log n)\)。
你知道吗？ 如果二叉树非常“不平衡”（例如每个节点都只有右子节点），它基本上就变成了一个列表，搜索速度会退化回 \(O(n)\)！
重点总结：
二叉树搜索使用分支结构来寻找数据。只要树保持平衡，其时间复杂度通常为 \(O(\log n)\)。
快速复习表
算法：线性搜索
是否需要数据排序？ 否
时间复杂度： \(O(n)\)
算法：二分搜索
是否需要数据排序？ 是
时间复杂度： \(O(\log n)\)
算法：二叉树搜索
是否需要数据排序？ 不适用（数据已在树结构中组织）
时间复杂度： \(O(\log n)\)
总结：我该选哪一个？
1. 如果数据量很小或未排序，请使用线性搜索。
2. 如果数据量很大且已在数组中排序完毕，请使用二分搜索。
3. 如果你需要频繁地添加和移除项目，同时还要保持搜索功能，那么二叉树通常是最好的选择。
如果刚开始觉得这些概念很棘手，别担心！最好的学习方法是尝试画出一组数字，并用手指模拟二分搜索的步骤。你会发现搜索范围缩小的速度有多快！