Search Algorithms | 搜索算法考点精讲

📚 Search Algorithms | 搜索算法考点精讲

Search algorithms are fundamental to computer science, forming the backbone of data retrieval in everything from databases to web engines. For IB and OCR Computer Science students, mastering these algorithms means understanding not just how they work, but also when and why to use each one, along with their computational efficiency. This article unpacks key searching techniques, compares their performance, and highlights common exam pitfalls.

搜索算法是计算机科学的基础，构成了从数据库到网络引擎等数据检索的核心。对于 IB 和 OCR 计算机科学学生而言，掌握这些算法不仅意味着理解它们如何工作，还要知道何时以及为何使用它们，并了解其计算效率。本文将剖析关键搜索技术，比较它们的性能，并指出常见的考试陷阱。

1. Linear Search: The Brute Force Approach | 线性搜索：暴力破解法

A linear search checks each element of a list sequentially until the target is found or the list ends. It works on any data structure that supports iteration, sorted or unsorted, making it universally applicable but inefficient for large datasets. The worst-case time complexity is O(n), where n is the number of elements, because in the worst case the target may be the last element or absent entirely.

线性搜索会按顺序检查列表中的每个元素，直到找到目标或列表结束。它适用于支持迭代的任何数据结构，无论是否已排序，因此通用性强，但面对大数据集时效率低下。最坏情况时间复杂度为 O(n)，其中 n 是元素个数，因为最坏情况下目标可能是最后一个元素或根本不存在。

• Best-case: O(1) – target at first position.
• Worst-case: O(n) – target at end or not present.
• Average: O(n).
• Space complexity: O(1) – only a few variables needed.
• 最佳情况：O(1) – 目标在第一个位置。
• 最坏情况：O(n) – 目标在末尾或不存在。
• 平均情况：O(n)。
• 空间复杂度：O(1) – 仅需少量变量。

2. Binary Search: Divide and Conquer | 二分搜索：分而治之

Binary search requires a sorted array. It repeatedly divides the search interval in half, comparing the target with the middle element. If the target equals the middle, the search ends; if less, search the left half; if greater, search the right half. This logarithmic reduction makes it dramatically faster on large, ordered datasets, with a time complexity of O(log n).

二分搜索要求数组已排序。它反复将搜索区间一分为二，将目标与中间元素比较。如果目标等于中间值，搜索结束；如果较小，搜索左半部；如果较大，搜索右半部。这种对数级的缩减使其在大规模有序数据集上极快，时间复杂度为 O(log n)。

• Precondition: data must be sorted.
• Time complexity: O(log n) – worst and average case.
• Space complexity: O(1) for iterative; O(log n) for recursive (call stack).
• 前提条件：数据必须有序。
• 时间复杂度：O(log n) – 最坏和平均情况。
• 空间复杂度：迭代为 O(1)；递归为 O(log n)（调用栈）。

3. Comparing Linear and Binary Search | 线性搜索与二分搜索对比

The choice between linear and binary search hinges on whether the data is sorted and how large it is. For tiny arrays, linear search may outperform binary search due to lower overhead. However, as n grows, the O(log n) advantage of binary search becomes immense. For instance, searching 1 million elements takes at most ~20 comparisons with binary search, versus up to 1 million with linear.

选择线性搜索还是二分搜索取决于数据是否有序以及数据量大小。对于极小的数组，由于开销较低，线性搜索可能比二分搜索更快。但随着 n 增大，二分搜索的 O(log n) 优势变得巨大。例如，在 100 万个元素中，二分搜索最多只需约 20 次比较，而线性搜索最多需要 100 万次。

Aspect	Linear Search	Binary Search
Data requirement	None (unsorted ok)	Must be sorted
Time (worst)	O(n)	O(log n)
Use case	Small data, linked lists	Large sorted arrays

4. Implementing Binary Search Iteratively | 迭代实现二分搜索

An iterative binary search uses a loop to adjust low and high pointers until the target is found or pointers cross. This avoids the overhead of recursive function calls and uses constant extra space. Exam boards often expect students to write pseudocode with correct mid-point calculation, typically mid = low + (high – low) / 2 to prevent integer overflow, though simpler expressions may be accepted in pseudocode.

迭代式二分搜索使用循环调整低位和高位指针，直到找到目标或指针交叉。这避免了递归函数调用的开销，并使用固定的额外空间。考试通常要求学生编写正确的伪代码，中间值计算通常为 mid = low + (high – low) / 2 以防止整数溢出，不过在伪代码中更简单的表达式也可以接受。

mid = low + (high – low) / 2

Key steps: initialise low = 0, high = length−1; while low ≤ high: calculate mid, if array[mid] == target return mid, else if target < array[mid], high = mid−1, else low = mid+1. If loop ends, return −1 (not found).

关键步骤：初始化 low = 0, high = length−1；当 low ≤ high 时：计算 mid，如果 array[mid] == target 返回 mid，否则如果 target < array[mid] 则 high = mid−1，否则 low = mid+1。循环结束后返回 −1（未找到）。

5. Recursive Binary Search | 递归二分搜索

A recursive implementation calls itself with updated boundaries. Although elegant and closely mirroring the mathematical definition, it consumes O(log n) stack space. Students must be able to trace recursive calls and state the base case explicitly: if low > high, return failure.

递归实现会使用更新后的边界调用自身。虽然形式优雅且紧密贴合数学定义，但它会消耗 O(log n) 的栈空间。学生必须能够跟踪递归调用，并明确说明基本情况：如果 low > high，返回查找失败。

Pseudocode pattern: binarySearch(arr, low, high, target) → if low > high return −1; mid = low + (high−low)/2; if arr[mid] == target return mid; else if target < arr[mid] return binarySearch(arr, low, mid−1, target); else return binarySearch(arr, mid+1, high, target).

伪代码模式：binarySearch(arr, low, high, target) → 如果 low > high 返回 −1；mid = low + (high−low)/2；如果 arr[mid] == target 返回 mid；否则如果 target < arr[mid] 返回 binarySearch(arr, low, mid−1, target)；否则返回 binarySearch(arr, mid+1, high, target)。

6. Searching in Binary Search Trees | 二叉搜索树中的搜索

A Binary Search Tree (BST) naturally supports efficient searching: at each node, if the target equals the node’s key, return it; if less, go left; if greater, go right. The search time depends on the tree’s height. In a balanced BST, height ≈ log₂ n, giving O(log n) search. However, if the tree degenerates into a linked list, worst-case O(n) occurs.

二叉搜索树（BST）天然支持高效搜索：在每个节点，如果目标等于节点的键值则返回；如果较小则转向左子树；如果较大则转向右子树。搜索时间取决于树的高度。在平衡的 BST 中，高度 ≈ log₂ n，搜索时间复杂度为 O(log n)。但如果树退化为链表，最坏情况会变成 O(n)。

A common exam mistake is assuming BST search is always O(log n). It is only true for balanced trees. Operations like self-balancing (AVL, Red-Black) maintain logarithmic height.

一个常见的考试错误是认为 BST 搜索总是 O(log n)。这只在平衡树中成立。自平衡操作（如 AVL、红黑树）可以维持对数高度。

7. Hashing and Constant‑Time Search | 哈希与常数时间搜索

Hash tables use a hash function to map keys to array indices, providing expected O(1) search. The target key is hashed, the index computed, and the value accessed directly. Collisions (different keys mapped to the same index) are handled via chaining or open addressing. Worst-case O(n) occurs if all keys collide, but with a good hash function and load factor control, this is rare.

哈希表使用哈希函数将键映射到数组索引，提供期望的 O(1) 搜索。目标键被哈希化，计算出索引，然后直接访问值。冲突（不同键映射到同一索引）通过链表法或开放寻址法处理。如果所有键都发生冲突，最坏情况为 O(n)，但在良好的哈希函数和装载因子控制下这种情况非常罕见。

OCR and IB syllabi require understanding of hashing principles, collision resolution, and when hash tables outperform BSTs or arrays. They are ideal when fast key-based lookup is needed and ordering is not required.

OCR 和 IB 教学大纲要求学生理解哈希原理、冲突解决方法，以及哈希表何时优于 BST 或数组。当需要基于键的快速查找且不需要排序时，哈希表是理想选择。

8. Searching in Unsorted vs Sorted Data | 无序数据与有序数据的搜索

When data is unsorted, linear search is the only practical option in simple data structures. If preprocessing (sorting) is allowed, we can sort once (O(n log n)) and then perform many O(log n) binary searches. This trade‑off is crucial: for a single query, sorting is wasteful; for repeated queries, the initial sorting cost pays off. IB papers often present scenarios asking which search strategy is optimal.

当数据无序时，线性搜索是简单数据结构中唯一可行的选择。如果允许预处理（排序），我们可以先进行 O(n log n) 的排序，然后执行多次 O(log n) 的二分搜索。这种权衡至关重要：对于单次查询，排序是浪费的；对于重复查询，初始排序成本是值得的。IB 试卷经常给出场景，询问哪种搜索策略最优。

Similarly, dynamic data (frequent insertions/deletions) may favour structures that maintain order automatically, like BSTs, where insert and search are both O(log n).

类似地，动态数据（频繁插入/删除）可能更适合使用自动维护顺序的结构，如 BST，其插入和搜索均为 O(log n)。

9. Space Complexity Considerations | 空间复杂度考量

While algorithmic searches like linear and binary search require minimal extra memory (O(1) iterative), some search structures trade space for time. Hash tables typically allocate a large internal array to minimise collisions, using O(n) space. Binary search trees add O(n) pointers. Understanding space‑time trade‑offs is essential for both IB and OCR evaluations, especially in memory‑constrained environments.

尽管线性搜索和二分搜索等算法搜索只需极少的额外内存（迭代实现 O(1)），但有些搜索结构会用空间换取时间。哈希表通常分配较大的内部数组以减少冲突，空间复杂度为 O(n)。二叉搜索树添加了 O(n) 的指针空间。理解时空权衡对于 IB 和 OCR 的评估至关重要，特别是在内存受限的环境中。

10. Common Exam Pitfalls and Tips | 常见考试陷阱与提示

One frequent mistake is applying binary search to an unsorted list without sorting first. Another is miscalculating the number of steps in binary search; remember it’s logarithmic, not a fixed number. Students also confuse search efficiency with sorting efficiency, or forget to mention the precondition of sortedness. Always state assumptions and analyse worst‑case scenarios explicitly.

一个常见错误是将二分搜索应用于未排序的列表而没有先排序。另一个错误是错误计算二分搜索的步数；记住它是对数级的，不是固定数字。学生还会混淆搜索效率与排序效率，或者忘记提及有序的前提条件。务必陈述假设并明确分析最坏情况。

When tracing algorithms, use a table to track low, high, mid, and array[mid] at each iteration. This prevents off‑by‑one errors and helps secure marks on dry‑run questions.

在跟踪算法时，使用表格记录每次迭代的 low、high、mid 以及 array[mid] 的值。这可以防止边界错误，并有助于在走查题中获取分数。

11. Searching Beyond Arrays: Graphs and Strings | 超越数组的搜索：图与字符串

Search extends beyond simple lists. Graph traversal algorithms like Depth‑First Search (DFS) and Breadth‑First Search (BFS) systematically explore nodes. String searching (e.g., Naïve, Knuth‑Morris‑Pratt) looks for patterns within text. While advanced, OCR A‑Level and IB Higher Level may touch upon these, expecting basic understanding of how searching generalises to more complex structures.

搜索不仅限于简单列表。图遍历算法如深度优先搜索（DFS）和广度优先搜索（BFS）会系统地探究节点。字符串搜索（如朴素算法、KMP 算法）在文本中查找模式。尽管这些内容较高级，OCR A‑Level 和 IB 高级课程可能会有所涉及，要求基本理解搜索如何推广到更复杂的结构。

12. Summary and Key Takeaways | 总结与关键要点

Search algorithms form a core skill in computer science. Linear search is simple and universal; binary search is exponentially faster but requires sorted data; BSTs and hash tables offer organised storage with rapid retrieval. The key is matching the algorithm to the data properties and operations required. Always consider time complexity, space complexity, and preconditions when choosing or justifying a search method.

搜索算法是计算机科学的核心技能。线性搜索简单通用；二分搜索速度指数级更快，但要求数据有序；BST 和哈希表提供有组织的存储和快速检索。关键是将算法与数据属性及所需操作相匹配。在选择或论证搜索方法时，始终考虑时间复杂度、空间复杂度和前置条件。

---

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）