GCSE CCEA Computer Science: Search | 搜索考点精讲

📚 GCSE CCEA Computer Science: Search | 搜索考点精讲

Searching is a fundamental operation in computer science, involving the process of finding a specific item from a collection of data. In the GCSE CCEA Computer Science specification, you are expected to understand, trace, and compare two essential search algorithms: linear search and binary search. Mastery of these algorithms helps you write efficient code and answer exam questions confidently.

搜索是计算机科学中的一项基本操作，指从一组数据中查找特定项目的过程。根据 GCSE CCEA 计算机科学大纲，你需要理解、跟踪并比较两种核心搜索算法：线性搜索与二分搜索。掌握这些算法有助于编写高效代码并充满信心地解答考题。

1. Introduction to Searching | 搜索简介

Searching is the process of finding a particular data item, known as the search key, within a dataset. In programming, this often involves iterating through arrays or lists to check if an element matches the target. The efficiency of a search algorithm can significantly impact program performance, especially with large datasets.

搜索是指在数据集中查找特定数据项（称为搜索关键字）的过程。在编程中，这通常涉及遍历数组或列表，检查元素是否与目标匹配。搜索算法的效率会严重影响程序性能，尤其是在处理大型数据集时。

In the CCEA GCSE specification, you are required to understand two search algorithms: linear search and binary search. You should be able to describe how they work, trace their execution, analyse their efficiency, and decide when to use each one.

在 CCEA 的 GCSE 大纲中，你需要理解两种搜索算法：线性搜索和二分搜索。你应能描述其工作原理、跟踪其执行过程、分析其效率，并决定何时使用每种算法。

2. What is Linear Search? | 什么是线性搜索？

Linear search (also called sequential search) is the simplest search algorithm. It checks each element of a list one by one, from the first to the last, until the target value is found or the end of the list is reached.

线性搜索（也称顺序搜索）是最简单的搜索算法。它会逐一检查列表中的每个元素，从第一个到最后一个，直到找到目标值或到达列表末尾。

Because it does not require the data to be sorted, linear search can be applied to any list. It is easy to implement but can be slow for very large datasets.

由于线性搜索不要求数据事先排序，因此可应用于任何列表。它易于实现，但在数据集非常大时可能很慢。

3. Linear Search Algorithm Steps | 线性搜索算法步骤

Start at the first element (index 0).

从第一个元素（索引 0）开始。
Compare the current element with the target value.

将当前元素与目标值进行比较。
If they match, return the index (or indicate found).

如果匹配，则返回索引（或指示已找到）。
If they do not match, move to the next element.

如果不匹配，则移至下一个元素。
Repeat until the target is found or the end of the list is reached.

重复此过程，直至找到目标或到达列表末尾。
If the list ends without a match, return a value such as -1 to indicate ‘not found’.

如果列表遍历完毕仍未匹配，则返回一个值（如 -1）表示“未找到”。

4. Linear Search Example and Trace Table | 线性搜索示例与跟踪表

Consider an array: [4, 2, 7, 1, 9] and we want to search for the value 7. Linear search will examine each element in order.

考虑数组：[4, 2, 7, 1, 9]，我们要搜索值 7。线性搜索将按顺序检查每个元素。

Index 0: element = 4, not equal to 7. Move to index 1.

索引 0：元素 = 4，不等于 7。移至索引 1。

Index 1: element = 2, not equal to 7. Move to index 2.

索引 1：元素 = 2，不等于 7。移至索引 2。

Index 2: element = 7, equals target. Return index 2.

索引 2：元素 = 7，等于目标。返回索引 2。

If we were searching for 5, the algorithm would check all elements and finally return -1.

如果搜索 5，算法将检查所有元素，最后返回 -1。

Pass 1: check 4, no match

第 1 次：检查 4，不匹配
Pass 2: check 2, no match

第 2 次：检查 2，不匹配
Pass 3: check 7, match found at index 2

第 3 次：检查 7，在索引 2 处找到匹配

5. Linear Search Efficiency | 线性搜索效率

The efficiency of linear search is measured by the number of comparisons. In the worst case, every element must be checked once, so for a list of length n, the worst-case complexity is O(n).

线性搜索的效率以比较次数衡量。在最坏情况下，必须检查每个元素一次，因此对于长度为 n 的列表，最坏情况复杂度为 O(n)。

In the best case, the target is at the first position, requiring only one comparison. On average, it requires n/2 comparisons.

最佳情况是目标位于第一个位置，只需一次比较。平均情况下，需要大约 n/2 次比较。

Linear search is inefficient for large sorted datasets, but it is the only option if the data is unsorted.

对于大型已排序数据集，线性搜索效率较低，但如果数据未排序，它是唯一的选择。

6. What is Binary Search? | 什么是二分搜索？

Binary search is a much more efficient algorithm, but it requires the data to be sorted in ascending order (or descending). It works by repeatedly dividing the search interval in half, discarding the half that cannot contain the target.

二分搜索是一种效率更高的算法，但它要求数据按升序（或降序）排列。它通过反复将搜索区间对半分，并丢弃不可能包含目标的那一半来工作。

Binary search is an example of a ‘divide and conquer’ algorithm. Each step reduces the search space by half, making it extremely fast for large lists.

二分搜索是“分治法”算法的一个例子。每一步都将搜索空间缩小一半，因此对于大型列表速度极快。

7. Binary Search Precondition and Steps | 二分搜索前提与步骤

Precondition: The list must be sorted in ascending order. If the data is not sorted, binary search will not work correctly.

前提条件：列表必须按升序排序。如果数据未排序，二分搜索将无法正确工作。

Steps of binary search:

二分搜索的步骤：

Identify the middle element of the current search range.

确定当前搜索范围的中间元素。
Compare the middle element with the target.

将中间元素与目标比较。
If they match, return the middle index.

如果匹配，返回中间索引。
If the target is smaller than the middle element, repeat the search on the left half.

如果目标小于中间元素，则在左半部分重复搜索。
If the target is larger, repeat on the right half.

如果目标大于，则在右半部分重复。
Continue until the target is found or the sublist reduces to zero size.

继续直到找到目标或子列表长度变为零。

8. Binary Search Example and Trace | 二分搜索示例与跟踪

Consider a sorted array: [1, 3, 5, 7, 9, 11, 13] and we search for 7. The search range starts with low = 0, high = 6.

考虑一个已排序数组：[1, 3, 5, 7, 9, 11, 13]，搜索 7。搜索范围初始 low = 0, high = 6。

Step 1: Mid = (0+6)//2 = 3. Element at index 3 is 7. Match found, so return 3.

步骤 1：中间 = (0+6)//2 = 3。索引 3 的元素是 7。匹配，返回 3。

Now search for 5. Low=0, high=6, mid=3, element=7. Since 5 < 7, high = mid-1 = 2. New range [0,2]. Mid=(0+2)//2=1, element=3. 5 > 3, so low = mid+1 =

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

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

GCSE CCEA Computer Science: Search | 搜索考点精讲