Search Algorithms | 搜索算法考点精讲

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

Search algorithms are fundamental to computer science, enabling programs to locate specific items within data collections. In the AQA GCSE Computer Science specification, you need to understand two core searching methods: linear search and binary search. You must be able to describe each algorithm step-by-step, apply them to small datasets, and compare their efficiency in different scenarios. This revision guide breaks down everything you need to know, from the logic behind each search to exam-style questions and common pitfalls.

搜索算法是计算机科学的基础，能够让程序在数据集合中定位特定项目。在 AQA GCSE 计算机科学考试大纲中，你需要掌握两种核心搜索方法：线性搜索和二分查找。你必须能够逐步描述每种算法，将它们应用于小规模数据集，并比较它们在不同场景下的效率。这份复习指南详细讲解了你需要知道的所有内容，从每种搜索背后的逻辑到考试式样的问题和常见错误。

1. What is a Search Algorithm? | 什么是搜索算法？

A search algorithm is a step-by-step procedure used to locate a specific element within a data structure, such as an array or list. The algorithm takes the data set and a target value as input, and returns the position (index) of the target if found, or a message indicating it is not present. Choosing the right search method depends on whether the data is sorted or unsorted, as well as the size of the dataset.

搜索算法是一种逐步执行的过程，用于在数据结构（如数组或列表）中定位特定元素。该算法以数据集和目标值作为输入，如果找到目标则返回其位置（索引），否则返回一条表示目标不存在的消息。选择正确的搜索方法取决于数据是否已排序以及数据集的大小。

In GCSE exam papers, you will be typically given a list of numbers or strings and asked to trace the execution of a given search. You may also be asked to write pseudocode or discuss advantages and disadvantages.

在 GCSE 试卷中，通常会给出一个数字或字符串列表，要求追踪给定搜索的执行过程。你还可能被要求编写伪代码，或讨论优缺点。

2. Linear Search Algorithm | 线性搜索算法

A linear search (also known as sequential search) works by checking each element of the list one by one, in order, until the target value is found or the end of the list is reached. It does not require the data to be sorted, making it versatile for any type of list. The algorithm keeps track of the current index and compares the element at that index to the target.

线性搜索（也称为顺序搜索）的工作原理是按顺序逐个检查列表中的每个元素，直到找到目标值或到达列表末尾。它不要求数据已排序，因此适用于任何类型的列表。该算法跟踪当前索引，并将该索引处的元素与目标进行比较。

For a list of n elements, in the worst case (target at the very end or not present) the algorithm makes n comparisons. The best case is 1 comparison when the target is at the beginning. On average, it will take n/2 comparisons. This is described as having a time complexity of O(n) – proportional to the size of the list.

对于包含 n 个元素的列表，在最坏情况下（目标在末尾或不存在），算法需要进行 n 次比较。当目标在开头时，最佳情况为 1 次比较。平均情况下，大约需要 n/2 次比较。这被称为时间复杂度为 O(n) – 与列表大小成正比。

The steps for linear search:

线性搜索的步骤：

Start at the first element (index 0).
从第一个元素（索引 0）开始。
Compare the current element with the target value.
将当前元素与目标值进行比较。
If they match, return the current index.
如果匹配，返回当前索引。
If they don’t match, move to the next element.
如果不匹配，移动到下一个元素。
Repeat until the target is found or the end of the list is reached.
重复直到找到目标或到达列表末尾。
If the target is not found, return ‘not found’ or a suitable sentinel value such as -1.
如果未找到目标，返回“未找到”或适当的哨兵值，如 -1。

Example: searching for 7 in the list [4, 2, 7, 1, 5]. Check index 0 (4) → no, index 1 (2) → no, index 2 (7) → yes, return 2.

示例：在列表 [4, 2, 7, 1, 5] 中搜索 7。检查索引 0（4）→ 否，索引 1（2）→ 否，索引 2（7）→ 是，返回 2。

3. Binary Search Algorithm | 二分查找算法

Binary search is a much more efficient algorithm, but it only works on sorted data. It works by repeatedly dividing the search interval in half. Initially, the interval covers the whole list. If the value of the search key is less than the item in the middle of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. The process continues until the value is found or the interval is empty.

二分查找是一种高效得多的算法，但仅适用于已排序的数据。它通过反复将搜索区间缩小一半来工作。最初，区间覆盖整个列表。如果搜索键的值小于区间中间的元素，则将区间缩小到下半部分。否则，缩到上半部分。此过程持续到找到该值或区间为空。

The binary search algorithm requires three pointers or indices: low (start of the list), high (end of the list), and mid (calculated as the middle index). The mid index is usually found using integer division: mid = (low + high) // 2. In the GCSE pseudocode exam reference language, this is often written as MIDDLE ← INTEGER((FIRST + LAST) / 2) or similar.

二分查找算法需要三个指针或索引：low（列表开头）、high（列表末尾）和 mid（计算出的中间索引）。mid 索引通常通过整数除法得到：mid = (low + high) // 2。在 GCSE 伪代码考试参考语言中，通常写作 MIDDLE ← INTEGER((FIRST + LAST) / 2) 或类似形式。

Time complexity for binary search is O(log n) – very efficient even on large datasets, because each comparison halves the remaining search space.

二分查找的时间复杂度为 O(log n) – 即使在大型数据集上也非常高效，因为每次比较都会将剩余搜索空间减半。

The steps for binary search:

二分查找的步骤：

Set low = 0, high = length of list – 1.
设置 low = 0，high = 列表长度 – 1。
While low ≤ high, repeat:
当 low ≤ high 时，重复：
Calculate mid = (low + high) // 2.
计算 mid = (low + high) // 2。
If list[mid] equals target, return mid.
如果 list[mid] 等于目标，返回 mid。
Else if list[mid] < target, set low = mid + 1.
否则如果 list[mid] < 目标，设置 low = mid + 1。
Else set high = mid – 1.
否则设置 high = mid – 1。
If low > high, target not found.
如果 low > high，目标未找到。

4. Binary Search Example Walkthrough | 二分查找示例走查

Let’s search for the value 23 in the sorted list [3, 8, 12, 15, 19, 23, 30, 41].

让我们在已排序列表 [3, 8, 12, 15, 19, 23, 30, 41] 中搜索值 23。

Initial: low = 0, high = 7. mid = (0+7)//2 = 3. list[3] = 15. 23 > 15, so discard lower half: low = mid + 1 = 4.

初始：low = 0，high = 7。mid = (0+7)//2 = 3。list[3] = 15。23 > 15，因此舍弃下半部分：low = mid + 1 = 4。

Second iteration: low = 4, high = 7. mid = (4+7)//2 = 5. list[5] = 23. Match found! Return 5.

第二次迭代：low = 4，high = 7。mid = (4+7)//2 = 5。list[5] = 23。匹配！返回 5。

If the target were 20 (not present), the steps would eventually lead to low > high. At one stage low=4, high=4 (mid=4, value 19). Since 20 > 19, low becomes 5. Now low=5, high=4. Loop condition fails → not found.

如果目标是 20（不存在），这些步骤最终会导致 low > high。在某个阶段 low=4，high=4（mid=4，值为 19）。因为 20 > 19，low 变为 5。现在 low=5，high=4。循环条件失败 → 未找到。

5. Pseudocode for Linear Search | 线性搜索伪代码

Linear search pseudocode as you might see in an AQA paper:

线性搜索伪代码，你可能在 AQA 试卷上看到：

i ← 0
WHILE i < LEN(list) AND list[i] ≠ target
i ← i + 1
ENDWHILE
IF i < LEN(list) THEN
OUTPUT i
ELSE
OUTPUT “Not found”
ENDIF

This version uses a while loop that continues as long as the item hasn’t been found and the end hasn’t been reached. After the loop, an if statement checks whether we found the item. Some variations may use a flag variable like ‘found’ and break out of the loop.

这个版本使用了一个 while 循环，只要未找到项目且未到达末尾就继续。循环结束后，使用 if 语句检查是否找到了该项目。有些变体可能使用像 ‘found’ 这样的标志变量并跳出循环。

6. Pseudocode for Binary Search | 二分查找伪代码

Binary search pseudocode, often required in exam responses:

二分查找伪代码，常在考试答案中要求：

low ← 0
high ← LEN(list) – 1
found ← FALSE
WHILE low ≤ high AND found = FALSE
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← TRUE
ELSE IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid – 1
ENDIF
ENDWHILE
IF found THEN OUTPUT mid ELSE OUTPUT “Not found”

Note the use of DIV for integer division, and the flag variable ‘found’ to control loop termination. Some AQA mark schemes allow using a RETURN statement inside the loop, which would exit the subroutine immediately.

注意使用 DIV 进行整数除法，以及使用标志变量 ‘found’ 来控制循环终止。一些 AQA 评分方案允许在循环内部使用 RETURN 语句，这将立即退出子程序。

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

The key differences between linear search and binary search are essential for exam success. You need to be able to discuss them clearly.

线性搜索和二分查找之间的关键区别对于考试成功至关重要，你需要能够清晰地讨论它们。

Linear Search	Binary Search
Works on unsorted and sorted data	Requires data to be sorted
Slower for large data sets (O(n))	Much faster for large data sets (O(log n))
Simple to implement and understand	More complex logic
Best case: 1 comparison	Best case: 1 comparison (if middle)
Worst case: n comparisons	Worst case: log₂ n comparisons

If the data is unsorted and you need to search, you must use linear search. But if you have the ability to sort the data first, then binary search becomes very attractive for repeated searches. However, sorting itself takes time (typically O(n log n)).

如果数据未排序且你需要搜索，必须使用线性搜索。但如果你能够先对数据排序，那么二分查找对于重复搜索就非常有吸引力。然而，排序本身也需要时间（通常为 O(n log n)）。

8. Applying Search Algorithms in Exam Questions | 在考试问题中应用搜索算法

Typical AQA exam questions might ask you to fill in trace tables, identify the number of comparisons made, or correct erroneous pseudocode. You should be precise with indices: remember that indices start at 0 in most exam contexts unless stated otherwise. When tracing, show each value change of low, high, mid, and any output.

典型的 AQA 考试题目可能要求你填写追踪表、确定比较次数或纠正错误的伪代码。你应该注意索引的准确性：除非另有说明，在大多数考试情境中索引从 0 开始。在进行追踪时，展示 low、high、mid 以及任何输出的每一次值变化。

For example: “Describe how a binary search would find the number 18 in the list [2, 5, 9, 14, 18, 22, 27].” You would show the initial pointers and then each iteration, concluding with the index 4.

例如：“描述二分查找如何在列表 [2, 5, 9, 14, 18, 22, 27] 中找到数字 18。”你需要展示初始指针，然后每次迭代，最后以索引 4 结束。

Questions often ask “which algorithm is more suitable” given a scenario. Consider factors like whether the data is sorted, the size of the dataset, and how many searches will be performed.

问题常常问“哪种算法更合适”，并给定一个场景。要考虑数据是否已排序、数据集的大小以及将执行多少次搜索等因素。

9. Common Mistakes and How to Avoid Them | 常见错误及如何避免

Students often confuse the conditions for binary search – it must be sorted. Applying binary search to an unsorted list results in incorrect or unpredictable results. Another mistake is miscalculating the mid index: failing to use integer division or forgetting to add low back after halving. Ensure the algorithm always works within the correct bounds and that the condition low ≤ high includes equality, otherwise the last element might be missed.

学生经常混淆二分查找的条件 – 数据必须已排序。将二分查找应用于未排序列表会导致不正确或不可预测的结果。另一个错误是 miscalculating mid 指数：未使用整数除法或在减半后忘记加回 low。确保该算法始终在正确的边界内工作，并且条件 low ≤ high 包括等号，否则可能会遗漏最后一个元素。

When writing pseudocode, remember to initialise all variables. For binary search, initialise found to FALSE. For linear search, do not forget to increment the counter i. Also, avoid infinite loops by ensuring the counter or bounds change in each iteration.

在编写伪代码时，记得初始化所有变量。对于二分查找，将 found 初始化为 FALSE。对于线性搜索，不要忘记递增计数器 i。此外，通过确保每次迭代中计数器或边界发生变化来避免无限循环。

10. Practice Questions and Summary | 练习题目与总结

To reinforce your understanding, attempt these quick questions: 1) Write pseudocode for a linear search that returns a Boolean value indicating whether the target was found. 2) Trace a binary search for target 6 in the list [1, 3, 5, 7, 9] and state the result. 3) Explain why a linear search might be preferred over a binary search even when the data is sorted. (Hint: consider very small lists or the overhead of recursion/iteration).

为了巩固你的理解，请尝试以下快速问题：1) 编写一个线性搜索的伪代码，返回一个布尔值，指示是否找到了目标。2) 在列表 [1, 3, 5, 7, 9] 中追踪二分查找目标 6，并说明结果。3) 解释为什么即使数据已排序，线性搜索也可能比二分查找更受欢迎。（提示：考虑非常小的列表或递归/迭代的开销）。

Remember: linear search – simple, no sorting required, O(n). Binary search – fast, requires sorted data, O(log n). Both are fundamental and tested regularly. Being able to write and trace both in pseudocode is a core skill for Paper 1.

记住：线性搜索 – 简单，无需排序，O(n)。二分查找 – 快速，需要已排序数据，O(log n)。两者都是基础且经常被考查的知识点。能够用伪代码编写和追踪两者是试卷 1 的核心技能。

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

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

Search Algorithms | 搜索算法考点精讲