GCSE Computer Science: Search Algorithms | GCSE 计算机：搜索算法考点精讲

📚 GCSE Computer Science: Search Algorithms | GCSE 计算机：搜索算法考点精讲

Search algorithms are fundamental to computer science and a core topic in the GCSE Computer Science curriculum. They allow programs to find a specific data item within a collection, such as an array or list. Understanding how linear search and binary search work—and being able to compare their efficiency—is essential for both written exams and practical programming tasks. This article provides a comprehensive revision guide covering key concepts, step-by-step explanations, pseudocode, efficiency analysis, and exam tips.

搜索算法是计算机科学的基础，也是 GCSE 计算机科学课程的核心主题。它们使程序能够在数组或列表等数据集合中查找特定数据项。理解线性搜索和二分搜索的工作原理，并能够比较它们的效率，对于笔试和实践编程任务都至关重要。本文提供一份全面的复习指南，涵盖关键概念、逐步解析、伪代码、效率分析和考试技巧。

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

A search algorithm is a method for finding a target value within a data structure. In GCSE Computer Science, the focus is usually on searching through arrays or lists of items. The algorithm takes the collection and the item to find as input, and returns either the position of the item or an indication that the item is not present.

搜索算法是一种在数据结构中查找目标值的方法。在 GCSE 计算机科学中，重点通常是在数组或列表中搜索项目。算法将数据集合和要查找的项目作为输入，返回项目的位置或项目不存在的指示。

There are two main search algorithms you must know: linear search and binary search. They differ significantly in how they work, their efficiency, and the conditions under which they can be applied.

你必须掌握两种主要的搜索算法：线性搜索和二分搜索。它们在工作方式、效率以及适用条件上有显著差异。

2. Linear Search: Step-by-Step Process | 线性搜索：逐步过程

Linear search, also called sequential search, checks each element of the list one by one in order from the beginning until either the target is found or the whole list has been examined. It does not require the data to be sorted.

线性搜索，又称顺序搜索，从列表开头依次逐个检查每个元素，直到找到目标或检查完整个列表。它不要求数据已排序。

Imagine you have a list of numbers: [12, 34, 8, 19, 27] and you want to search for 19. Linear search would first check 12 (no match), then 34 (no), then 8 (no), then 19 (match found at index 3, if 0-based indexing). The search stops and returns the position.

假设有一个数字列表：[12, 34, 8, 19, 27]，要查找 19。线性搜索首先检查 12（不匹配），然后是 34（不），然后是 8（不），最后是 19（在索引 3 处找到匹配，若从 0 开始计数）。搜索停止并返回该位置。

If the target item is not in the list, the algorithm must check every single element before concluding the item is absent. This makes linear search simple but potentially slow for large lists.

如果目标项目不在列表中，算法必须检查完每一个元素才能得出项目不存在的结论。这使得线性搜索虽然简单，但对于大型列表可能较慢。

3. Linear Search Pseudocode and Implementation | 线性搜索伪代码与实现

In GCSE exams, you are often required to write or understand pseudocode for linear search. Here is a typical representation:

在 GCSE 考试中，经常要求你编写或理解线性搜索的伪代码。以下是一个典型表示：

FUNCTION linearSearch(arr, target)
FOR i ← 0 TO LEN(arr)-1
IF arr[i] = target THEN
RETURN i
ENDIF
ENDFOR
RETURN -1
ENDFUNCTION

The algorithm iterates through the array using an index i. If a match is found, the index is returned immediately. If the loop finishes without finding the target, -1 (or a similar sentinel value) is returned to indicate failure.

该算法使用索引 i 遍历数组。如果找到匹配，立即返回索引。如果循环结束仍未找到目标，则返回 -1（或类似的哨兵值）表示失败。

Note: The exam may use different syntax (e.g., OUTPUT instead of RETURN), but the logic remains the same.
注意：考试中可能使用不同的语法（如用 OUTPUT 代替 RETURN），但逻辑保持不变。

You should be able to trace this pseudocode with a given array and target value, showing the values of i and arr[i] at each step.

你应该能够用给定的数组和目标值来跟踪此伪代码，展示每一步中 i 和 arr[i] 的值。

4. Linear Search Efficiency and Use Cases | 线性搜索的效率与使用场景

The efficiency of a search algorithm is often described using Big O notation. For linear search, in the worst case, the algorithm must look at every element: O(n), where n is the number of items.

搜索算法的效率常用大 O 表示法来描述。对于线性搜索，在最坏情况下，算法必须检查每一个元素：O(n)，其中 n 是项的数量。

Best case: O(1) — the target is at the very first position. Average case: O(n) — roughly half the elements are checked.

最佳情况：O(1) — 目标恰好在第一个位置。平均情况：O(n) — 大约检查一半的元素。

Since linear search works on unsorted data and is straightforward to code, it is useful when:
– The dataset is small.
– The data is unsorted and cannot or should not be sorted.
– The list is expected to contain the target near the beginning.

由于线性搜索可用于未排序数据且编码简单，它在以下情况中很有用：
– 数据集较小。
– 数据未排序，并且不能或不应排序。
– 预计目标靠近列表开头。

In a GCSE programming task, if you just need to find one item in a short list, linear search is often perfectly acceptable.

在 GCSE 编程任务中，如果只需在短列表中查找一个项目，线性搜索通常完全可行。

5. Binary Search: Step-by-Step Process | 二分搜索：逐步过程

Binary search is a much faster algorithm, but it has a crucial precondition: the list must be sorted in ascending (or descending) order. It works by repeatedly dividing the search interval in half.

二分搜索是一种快得多的算法，但它有一个关键前提：列表必须按升序（或降序）排序。它通过不断将搜索区间对半分来工作。

Steps for binary search on a sorted array:
1. Find the middle element of the current search range.
2. If the middle element equals the target, the search is successful.
3. If the target is less than the middle element, discard the upper half; continue searching in the lower half.
4. If the target is greater, discard the lower half; continue in the upper half.
5. Repeat until the target is found or the range is empty (meaning the target is not present).

对已排序数组进行二分搜索的步骤：
1. 找出当前搜索范围的中间元素。
2. 如果中间元素等于目标，搜索成功。
3. 如果目标小于中间元素，舍弃上半部分；在下半部分继续搜索。
4. 如果目标大于中间元素，舍弃下半部分；在上半部分继续搜索。
5. 重复直到找到目标或范围为空（意味着目标不存在）。

Example: searching for 19 in sorted list [8, 12, 19, 27, 34].
– Middle index is 2 (value 19). 19 = target, found immediately.
If searching for 27:
– Middle 19 < 27, so look in upper half [27, 34]. - New middle is 27, found.

示例：在已排序列表 [8, 12, 19, 27, 34] 中搜索 19。
– 中间索引是 2（值 19）。19 = 目标，立即找到。
如果搜索 27：
– 中间 19 < 27，因此在 [27, 34] 中查找。 - 新中间是 27，找到。

6. Binary Search Pseudocode | 二分搜索伪代码

GCSE pseudocode for binary search often uses variables for the lower and upper bounds. Here is a common structure:

GCSE 的二分搜索伪代码通常使用下界和上界变量。以下是一个常见结构：

FUNCTION binarySearch(arr, target)
low ← 0
high ← LEN(arr) – 1
WHILE low ≤ high DO
mid ← (low + high) DIV 2
IF arr[mid] = target THEN
RETURN mid
ELSE IF arr[mid] < target THEN
low ← mid + 1
ELSE
high ← mid – 1
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION

Note the use of DIV for integer division. The condition low ≤ high ensures the search continues only while there is still a valid range. When low exceeds high, the target is not in the array.

注意使用 DIV 进行整数除法。条件 low ≤ high 确保只有当有效范围仍然存在时才继续搜索。当 low 超过 high 时，目标不在数组中。

In trace tables, you would record the values of low, high, mid, and arr[mid] at each iteration. This helps demonstrate understanding of the algorithm’s logic.

在跟踪表中，你会记录每次迭代中 low、high、mid 和 arr[mid] 的值。这有助于展示对算法逻辑的理解。

7. Binary Search Efficiency and Requirements | 二分搜索的效率与前提条件

The big O efficiency of binary search is O(log n). Each comparison halves the search space, so the number of steps grows very slowly even for large n. For a list of 1,000,000 items, binary search needs at most about 20 comparisons (since 2²⁰ ≈ 1,000,000).

二分搜索的大 O 效率是 O(log n)。每次比较将搜索空间减半，因此即使 n 很大，步骤数增长也非常缓慢。对于包含 1,000,000 个项的列表，二分搜索最多需要约 20 次比较（因为 2²⁰ ≈ 1,000,000）。

However, the initial requirement of a sorted list is a significant precondition. If the data is unsorted, sorting it first costs at least O(n log n) time, which may outweigh the benefit of fast searching unless many searches will be performed on the same sorted data.

然而，初始要求列表已排序是一个重要的前提条件。如果数据未排序，先对其进行排序至少需要 O(n log n) 时间，这可能抵消快速搜索的优势，除非要在同一已排序数据上执行多次搜索。

Binary search cannot be used on unsorted data; trying to do so will produce incorrect results.

二分搜索不能用于未排序的数据；尝试这样做会产生错误结果。

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

It is essential to choose the right search algorithm based on the situation. The table below summarizes the key differences:

根据情况选择合适的搜索算法至关重要。下表总结了关键区别：

Aspect 方面	Linear Search 线性搜索	Binary Search 二分搜索
Requirement 前提	Works on any list 适用于任何列表	List must be sorted 列表必须已排序
Complexity (worst case)	O(n)	O(log n)
Speed for large data 大数据速度	Slower 较慢	Very fast 非常快
Simplicity 简单性	Very simple 很简单	More complex 较复杂
Data structure 数据结构	Works on arrays and lists 适用于数组和列表	Typically on arrays with direct access 通常用于可随机访问的数组

In many exam questions, you will be asked to explain why one algorithm is more suitable than the other for a given scenario. Always mention the sorted/unsorted constraint and the efficiency difference.

在许多考试题目中，你会被要求解释为什么在给定场景下一种算法比另一种更合适。务必提及排序/未排序的约束以及效率差异。

9. Tracing Search Algorithms in Exams | 考试中的搜索算法跟踪

A common GCSE exam task is to complete a trace table for a search algorithm. You must be able to systematically record the state of variables and the output. Example for linear search: each row shows index i, arr[i], and whether it matches the target.

常见的 GCSE 考试任务是完成搜索算法的跟踪表。你必须能够系统地记录变量状态和输出。线性搜索示例：每行显示索引 i、arr[i] 以及是否匹配目标。

For binary search, you track low, high, mid, arr[mid], and the comparison result. The number of rows in a binary search trace is usually much smaller than in linear search for the same data, illustrating its efficiency.

对于二分搜索，你需要跟踪 low、high、mid、arr[mid] 和比较结果。对于相同数据，二分搜索跟踪表中的行数通常比线性搜索少得多，这说明了其效率。

When tracing, be careful with integer division and bounds updates. A typical exam mistake is forgetting to add/subtract 1 when adjusting low or high, leading to an infinite loop.

在跟踪时，注意整数除法和边界更新。一个典型的考试错误是在调整 low 或 high 时忘记加 1 或减 1，导致无限循环。

10. Variants and Extended Concepts | 变体与扩展概念

Although GCSE focuses on the standard forms, it is useful to know that linear search can be implemented with a sentinel to simplify the loop condition, and binary search can be performed recursively. However, for GCSE Computer Science, iterative binary search is the standard.

虽然 GCSE 侧重于标准形式，但了解一下线性搜索可以用哨兵来简化循环条件，二分搜索可以递归实现是有益的。然而，对于 GCSE 计算机科学，迭代二分搜索是标准。

Searching is just one type of algorithm alongside sorting. Often, search and sort algorithms are taught together. Remember that once you have sorted data (using e.g. bubble sort or merge sort), binary search becomes an option.

搜索只是与排序并列的一种算法。通常，搜索和排序算法是一起教的。记住，一旦你有了已排序的数据（例如使用冒泡排序或归并排序），二分搜索就成为一种选择。

In real-world applications, search algorithms are used in databases, search engines, and any system where fast data retrieval is needed. The concept of indexing builds on these ideas.

在实际应用中，搜索算法用于数据库、搜索引擎以及任何需要快速数据检索的系统。索引的概念建立在这些思想之上。

11. Exam-style Questions and Tips | 考试题型与技巧

1. “Describe the steps of a linear search to find the value X in an array.” – Answer with clear sequenced steps, mentioning starting at the first element and checking each in turn.

1. “描述在数组中用线性搜索查找值 X 的步骤。” – 用清晰的顺序步骤回答，提到从第一个元素开始依次检查每个元素。

2. “Explain why binary search cannot be used on an unsorted array.” – Because the process relies on comparing with the middle to decide which half to discard; if unsorted, you cannot guarantee that all elements to the left are smaller, so the logic breaks.

2. “解释为什么二分搜索不能用于未排序数组。” – 因为该过程依赖于与中间值比较来决定舍弃哪一半；如果未排序，无法保证左侧所有元素都更小，因此逻辑不成立。

3. “Compare the efficiency of linear and binary search.” – Provide Big O notations and discuss when each is preferred.

3. “比较线性搜索和二分搜索的效率。” – 提供大 O 表示法并讨论每种算法在何时更适用。

When writing pseudocode, use consistent indentation and clear variable names. In trace tables, fill every cell, showing unchanged variables as they were. Check the number of iterations carefully.

在编写伪代码时，使用一致的缩进和清晰的变量名。在跟踪表中，填写每个单元格，显示未改变的变量保持原值。仔细检查迭代次数。

12. Summary: Mastering Search for GCSE | 总结：掌握 GCSE 搜索算法

Search algorithms are a guaranteed topic in GCSE Computer Science. You need to know:
– Linear search: how it works, pseudocode, O(n) efficiency, works on any list.
– Binary search: how it works, pseudocode, O(log n) efficiency, requires a sorted list.
– How to trace both algorithms with given data.
– When to choose one over the other in a scenario.

搜索算法是 GCSE 计算机科学必考的主题。你需要了解：
– 线性搜索：工作原理、伪代码、O(n) 效率、适用于任何列表。
– 二分搜索：工作原理、伪代码、O(log n) 效率、需要已排序列表。
– 如何用给定数据跟踪这两种算法。
– 在场景中如何选择一种而不是另一种。

Review the pseudocode until you can write it from memory, and practice creating trace tables. Understanding the underlying logic will also help you approach unfamiliar problems in the exam. Both algorithms embody fundamental problem-solving strategies—sequential scanning and divide and conquer—that appear throughout the syllabus.

复习伪代码直到能够凭记忆写出，并练习创建跟踪表。理解底层逻辑也将帮助你在考试中应对陌生问题。这两种算法体现了贯穿整个大纲的基本问题解决策略——顺序扫描和分治法。

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

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

GCSE Computer Science: Search Algorithms | GCSE 计算机：搜索算法 考点精讲