📚 Search Algorithms for GCSE WJEC Computer Science | GCSE WJEC 计算机：搜索考点精讲
Searching is a fundamental operation in computer science that involves finding a specific data item within a collection. For GCSE WJEC Computer Science, you need to understand two key search algorithms: linear search and binary search. This revision guide explains both step by step, compares their efficiency, and prepares you for exam questions involving pseudocode and real-world scenarios.
搜索是计算机科学中的一项基本操作，指在数据集合中查找特定数据项。对于 GCSE WJEC 计算机科学，你需要掌握两种关键搜索算法：线性搜索和二分搜索。本复习指南将逐步解析这两种算法，比较它们的效率，并帮助你准备涉及伪代码和实际场景的考题。
1. Introduction to Search Algorithms | 搜索算法简介
A search algorithm is a method for finding a specific item, called the target, within a data structure such as a list or array. In the WJEC specification, you focus on two fundamental approaches: linear search (also known as sequential search) and binary search. These algorithms differ dramatically in their logic, performance, and prerequisites.
搜索算法是一种在列表或数组等数据结构中查找特定项目（目标）的方法。在 WJEC 考纲中，你需要重点关注两种基本方法：线性搜索（也称顺序搜索）和二分搜索。这些算法在逻辑、性能和前提条件上存在显著差异。
Understanding how search algorithms work is crucial because they form the basis of many larger programs, from simple contact lookup apps to complex database systems. Being able to choose the right search strategy can dramatically affect a program’s speed and resource usage.
理解搜索算法的工作原理至关重要，因为它们是许多大型程序的基础——从简单的联系人查找应用到复杂的数据库系统。能够选择合适的搜索策略可以显著影响程序的速度和资源占用。
2. Linear Search: Step-by-Step Explanation | 线性搜索：逐步解析
A linear search examines each element in a list one by one, starting from the first index (usually 0) and moving forward until the target is found or the list ends. It does not require the list to be sorted, making it applicable to any data set.
线性搜索会逐个检查列表中的每个元素，从第一个索引（通常为 0）开始，依次向后移动，直到找到目标或列表结束。它不要求列表已经排序，因此适用于任何数据集。
The basic algorithm can be expressed as:
FOR i ← 0 TO LENGTH(list)-1 IF list[i] = target THEN RETURN i ENDIFENDFORRETURN -1
基本算法可以表示为：
FOR i ← 0 TO LENGTH(list)-1 IF list[i] = target THEN RETURN i ENDIFENDFORRETURN -1
If the target is present, the algorithm returns the index of its first occurrence. If the loop finishes without finding the target, a sentinel value (commonly -1) indicates that the item is not in the list. The returned index can then be used for further processing.
如果目标存在，算法将返回它第一次出现时的索引。如果循环结束时仍未找到目标，则返回一个标记值（通常为 -1），表示该项不在列表中。随后便可以使用返回的索引进行进一步处理。
3. Linear Search Worked Example | 线性搜索实例演示
Consider the unsorted list [4, 2, 9, 7, 1, 5] and target value 7. A linear search proceeds as follows:
考虑未排序列表 [4, 2, 9, 7, 1, 5] 和目标值 7。线性搜索过程如下：
-
Index 0: value 4 does not equal 7 – continue.
索引 0：值 4 不等于 7 – 继续。
-
Index 1: value 2 does not equal 7 – continue.
索引 1：值 2 不等于 7 – 继续。
-
Index 2: value 9 does not equal 7 – continue.
索引 2：值 9 不等于 7 – 继续。
-
Index 3: value 7 equals 7 – target found, return index 3.
索引 3：值 7 等于 7 – 找到目标，返回索引 3。
Four comparisons were needed. If the target had been at the end of the list or absent, many more comparisons would have been required, illustrating the algorithm’s dependency on the position of the target.
共需要四次比较。如果目标位于列表末尾或根本不存在，则需要更多比较，这体现了算法对目标位置的依赖。
4. Linear Search Efficiency | 线性搜索的效率
The time complexity of linear search is expressed as O(n) in the worst and average cases, where n is the number of elements in the list. This means that in the worst case (target at the very end or not present), the algorithm will examine every single element.
线性搜索在最坏和平均情况下的时间复杂度为 O(n)，其中 n 为列表中的元素个数。这意味着在最坏情况下（目标在末尾或不存在），算法需要检查每一个元素。
Best-case performance occurs when the target is at index 0 – only one comparison is needed, giving O(1). However, because the list is unordered, you cannot predict where the target will be, so O(n) is the most relevant metric for large data sets.
最佳情况发生在目标位于索引 0 时——只需一次比较，时间复杂度为 O(1)。然而，由于列表无序，你无法预测目标的位置，因此对于大型数据集，O(n) 才是最能反映实际表现的指标。
Linear search is simple to implement and works on unsorted data, but its linear growth makes it impractical for very large lists. For small collections, it remains a perfectly reasonable choice.
线性搜索实现简单且可用于未排序数据，但其线性增长特性使其不适合处理极大型列表。对于小型数据集合，它依然是完全合理的选择。
5. Binary Search: Requirements and Core Concept | 二分搜索：前提条件与核心概念
Binary search works on the principle of divide and conquer, but it can only be applied to a sorted list. The algorithm repeatedly compares the target value with the middle element; if the target is smaller, the search continues in the left half, otherwise in the right half, discarding half of the remaining elements each time.
二分搜索基于分治原理，但只能用于已排序的列表。算法会将目标值与中间元素反复比较：如果目标较小，则在左半部分继续搜索，否则在右半部分继续，每次丢弃剩余元素的一半。
Because the list must be sorted, binary search is often used when data is already ordered, such as in a dictionary or a high-score table. If the list is unsorted, you must first sort it, which adds a preprocessing cost that may outweigh the benefits of faster searching.
由于列表必须排序，二分搜索通常用于数据已经有序的场景，例如字典或高分榜。如果列表未排序，你必须先排序，这会增加预处理开销，有时甚至会抵消快速搜索带来的好处。
6. Binary Search Step-by-Step Algorithm | 二分搜索逐步算法
A typical binary search algorithm maintains two pointers, low and high, that represent the current search interval. It computes the middle index and compares that element with the target, adjusting the interval after each comparison.
典型的二分搜索算法维护两个指针 low 和 high，它们代表当前搜索区间。算法计算中间索引，并将该位置的元素与目标比较，每次比较后调整区间。
Pseudocode for binary search:
low ← 0high ← LENGTH(list) - 1WHILE low ≤ high DO mid ← (low + high) DIV 2 IF list[mid] = target THEN RETURN mid ELSE IF list[mid] < target THEN low ← mid + 1 ELSE high ← mid - 1 ENDIFENDWHILERETURN -1
二分搜索的伪代码：
low ← 0high ← LENGTH(list) - 1WHILE low ≤ high DO mid ← (low + high) DIV 2 IF list[mid] = target THEN RETURN mid ELSE IF list[mid] < target THEN low ← mid + 1 ELSE high ← mid - 1 ENDIFENDWHILERETURN -1
The use of DIV ensures integer division, which is essential for calculating the middle index. The loop terminates either when the target is found or when the interval becomes invalid (low > high).
使用 DIV 可以确保整除，这对于计算中间索引至关重要。循环会在找到目标或区间无效（low > high）时终止。
7. Binary Search Worked Example | 二分搜索实例演示
Take the sorted list [1, 2, 4, 5, 7, 9] and target 7. The algorithm proceeds as shown:
以排序列表 [1, 2, 4, 5, 7, 9] 和目标 7 为例，算法过程如下所示：
(Indices: 0:1, 1:2, 2:4, 3:5, 4:7, 5:9)
（索引：0:1, 1:2, 2:4, 3:5, 4:7, 5:9）
| Iteration 迭代 |
Low 低 |
High 高 |
Mid 中 |
list[mid] 值 |
Action 操作 |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 4 | 4 < 7, so low ← mid + 1 = 3 4 < 7，所以 low 变为 3 |
| 2 | 3 | 5 | 4 | 7 | 7 = 7, target found at index 4 7 = 7，在索引 4 找到目标 |
Only two comparisons were required, compared with four for the linear search on even a small list. The advantage becomes much more dramatic as the list size grows.
只需要两次比较，而相同小列表的线性搜索则需要四次。随着列表增大，这种优势将变得更加显著。
8. Binary Search Efficiency | 二分搜索的效率
Binary search has a worst-case and average-case time complexity of O(log₂ n). Because the search space is halved at each step, the number of comparisons grows logarithmically with the number of elements.
二分搜索的最坏情况和平均情况时间复杂度为 O(log₂ n)。由于每一步搜索空间都会减半，比较次数的增长与元素数量成对数关系。
For example, a list of 1,000,000 elements requires at most about 20 comparisons, because 2²⁰ ≈ 1,048,576. In contrast, a linear search on the same list might need up to 1,000,000 comparisons in the worst case. This logarithmic scaling makes binary search extremely powerful for large, sorted datasets.
例如，包含 1,000,000 个元素的列表最多只需要约 20 次比较，因为 2²⁰ ≈ 1,048,576。相比之下，线性搜索在最坏情况下可能需要多达 1,000,000 次比较。这种对数级别的增长使得二分搜索在处理大型有序数据集时极为高效。
The best case is still O(1) if the target happens to be at the first mid-point examined. However, the guarantee of logarithmic search time is what sets binary search apart from linear search.
最佳情况依然是 O(1)，如果目标恰好位于第一个中间点。然而，保证对数级别的搜索时间正是二分搜索区别于线性搜索的关键所在。
9. Comparing Linear and Binary Search | 线性搜索与二分搜索对比
The table below summarises the key differences between the two algorithms, which are frequently assessed in WJEC exams.
下表总结了这两种算法之间的主要差异，这些差异在 WJEC 考试中经常出现。
| Feature 特征 |
Linear Search 线性搜索 |
Binary Search 二分搜索 |
|---|---|---|
| Requires sorted data? 需要排序？ |
No 否 |
Yes, must be sorted 是，必须已排序 |
| Time complexity (worst) 最坏时间复杂度 |
O(n) | O(log₂ n) |
| Best case 最佳情况 |
O(1) | O(1) |
| Implementation complexity 实现复杂度 |
Very simple 非常简单 |
Moderate 中等 |
| Suitable for 适用场景 |
Small or unsorted lists 小或未排序列表 |
Large, sorted lists 大型已排序列表 | Published by TutorHao | GCSE Computer Science Revision Series | aleveler.com
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导