📚 A-Level OCR Computer Science: Searching Algorithms Exam Revision | A-Level OCR 计算机：搜索算法考点精讲
Searching is a fundamental operation in computer science, allowing programs to locate specific items within a collection of data. In the OCR A-Level specification, you are expected to understand the principles, algorithms, and efficiency of two core search methods: linear search and binary search. This article provides a comprehensive revision guide, covering every key concept, common exam pitfalls, and the precise technical language required for top marks.
搜索是计算机科学中的基本操作，使程序能够在数据集合中定位特定条目。在 OCR A-Level 考试大纲中，你需要掌握两种核心搜索方法的原理、算法和效率：线性搜索和二分搜索。本文提供一份全面的复习指南，涵盖每个关键概念、常见考试陷阱以及获取高分所需的精确技术语言。
1. Introduction to Searching | 搜索算法简介
In computing, a search algorithm is a step-by-step method for finding a target value within a data structure, typically an array or list. The efficiency of a search depends on whether the data is sorted or unsorted. Two fundamental algorithms are examined in the OCR specification: linear search (for unsorted or sorted data) and binary search (exclusively for sorted data).
在计算中，搜索算法是一种在数据结构（通常是数组或列表）中寻找目标值的逐步方法。搜索的效率取决于数据是否已排序。OCR 考纲中考查两种基本算法：线性搜索（适用于未排序或已排序数据）和二分搜索（仅适用于已排序数据）。
2. Linear Search: The Simple Approach | 线性搜索：简单方法
Linear search, also known as sequential search, examines each element of a collection one by one until the target is found or the end is reached. It does not require the data to be sorted. In the worst case, when the item is at the very end or missing, every element must be checked.
线性搜索，也称为顺序搜索，逐个检查数据集合中的每一个元素，直到找到目标或到达末尾。它不要求数据已排序。在最坏情况下，当目标位于最末尾或不存在时，必须检查每一个元素。
To implement a linear search, you start at index 0 and compare the current item with the target. If a match is found, the index is returned. If the loop finishes without a match, a flag such as -1 is returned to indicate failure.
为了实现线性搜索，从索引 0 开始，将当前项与目标比较。如果找到匹配，返回该索引。如果循环结束仍未找到，则返回一个标志（如 -1）以表示失败。
3. Algorithm for Linear Search | 线性搜索算法
A typical pseudocode for linear search on an array A of length n, searching for target T:
FOR i ← 0 TO n-1
IF A[i] = T THEN
RETURN i
END FOR
RETURN -1
在一个长度为 n 的数组 A 中搜索目标 T 的典型线性搜索伪代码：
FOR i ← 0 TO n-1
IF A[i] = T THEN
RETURN i
END FOR
RETURN -1
The algorithm works equally well on unsorted and sorted data. Because it uses a simple loop, it is easy to implement and understand. However, its performance degrades linearly with the size of the dataset.
该算法在未排序和已排序数据上都能同样工作。由于它使用简单的循环，因此易于实现和理解。然而，其性能随数据集大小线性下降。
4. Performance of Linear Search | 线性搜索性能
Using Big O notation, the time complexity of linear search is O(n) in both the worst-case and average-case scenarios. The best-case occurs when the target is at the very beginning, giving O(1). Space complexity is O(1) because only a few extra variables are needed.
使用大 O 表示法，线性搜索在最坏情况和平均情况下的时间复杂度均为 O(n)。最佳情况发生在目标位于最开头时，时间复杂度为 O(1)。空间复杂度为 O(1)，因为只需要少量额外变量。
In an exam, you may be asked to calculate the maximum number of comparisons needed. For a list of size n, linear search requires at most n comparisons. If the item is not present, exactly n comparisons are performed before the search terminates.
在考试中，你可能会被要求计算所需的最大比较次数。对于大小为 n 的列表，线性搜索最多需要 n 次比较。如果目标不存在，则在进行恰好 n 次比较后搜索终止。
5. Binary Search: Divide and Conquer | 二分搜索：分而治之
Binary search is a far more efficient algorithm but requires the data to be sorted in ascending (or descending) order. It repeatedly divides the search interval in half, discarding the half that cannot contain the target. This ‘divide and conquer’ approach quickly narrows down the possible location.
二分搜索是一种效率高得多的算法，但要求数据已按升序（或降序）排列。它反复将搜索区间一分为二，丢弃不可能包含目标的那一半。这种“分而治之”的策略能迅速缩小可能的位置。
The algorithm uses two pointers, typically called low and high, that define the current search boundaries. A middle index is calculated, and the target is compared with the middle element. Depending on the comparison, either the left or right half is selected for the next iteration.
该算法使用两个指针，通常称为 low 和 high，它们定义了当前的搜索边界。计算中间索引，并将目标与中间元素进行比较。根据比较结果，选择左半部分或右半部分进行下一次迭代。
6. Algorithm for Binary Search | 二分搜索算法
Here is the standard iterative pseudocode for binary search on a sorted array A of n elements, target T:
low ← 0
high ← n-1
WHILE low ≤ high
mid ← (low + high) DIV 2
IF A[mid] = T THEN
RETURN mid
ELSE IF A[mid] < T THEN
low ← mid + 1
ELSE
high ← mid – 1
END WHILE
RETURN -1
以下是在包含 n 个元素的已排序数组 A 中搜索目标 T 的标准迭代伪代码：
low ← 0
high ← n-1
WHILE low ≤ high
mid ← (low + high) DIV 2
IF A[mid] = T THEN
RETURN mid
ELSE IF A[mid] < T THEN
low ← mid + 1
ELSE
high ← mid – 1
END WHILE
RETURN -1
Note the use of integer division (DIV) to find the middle index. The loop continues as long as the subarray is valid (low ≤ high). If the target is not found, -1 is returned.
请注意使用整数除法（DIV）来找到中间索引。只要子数组有效（low ≤ high），循环就会继续。如果未找到目标，则返回 -1。
7. Performance of Binary Search | 二分搜索性能
The time complexity of binary search is O(log n) in the worst case, which makes it dramatically faster than linear search for large datasets. Each iteration reduces the search space by half, so a list of 1,000,000 items requires at most about 20 comparisons.
二分搜索的最坏情况时间复杂度为 O(log n)，这使得它在大型数据集上比线性搜索快得多。每次迭代将搜索空间减半，因此一个包含 1,000,000 个元素的列表最多只需要大约 20 次比较。
The best-case time is O(1) when the middle element happens to be the target. Space complexity is O(1) for the iterative version, or O(log n) if implemented recursively due to call stack usage.
最佳情况是中间元素恰好为目标，时间复杂度为 O(1)。迭代版本的空间复杂度为 O(1)；如果使用递归实现，由于调用栈的占用，空间复杂度为 O(log n)。
8. Comparison of Linear and Binary Search | 线性与二分搜索对比
| Criteria / 标准 | Linear Search / 线性搜索 | Binary Search / 二分搜索 |
|---|---|---|
| Data requirement / 数据要求 | Works on unsorted or sorted data / 适用于未排序或已排序数据 | Requires sorted data / 要求已排序数据 |
| Time complexity (worst) / 时间复杂度（最坏） | O(n) | O(log n) |
| Number of comparisons on 1024 items / 1024个元素的比较次数 | Up to 1024 / 最多1024次 | Up to 11 / 最多11次 |
| Space complexity / 空间复杂度 | O(1) | O(1) iterative, O(log n) recursive / 迭代O(1)，递归O(log n) |
| Simplicity / 简易性 | Very simple to implement / 实现非常简单 | More complex, careful with boundaries / 较复杂，需注意边界 |
This table highlights why binary search is preferred for large sorted datasets, but linear search remains useful for small lists or when the sorting overhead cannot be justified.
该表格突显了为什么在大型已排序数据集中优先使用二分搜索，但对于小型列表或当排序开销不值得时，线性搜索仍然有用。
9. When to Use Each Search | 何时使用各搜索
Choose linear search when the data is unsorted and cannot be sorted (e.g., the original order must be preserved), or when the list is very small. Also, if you are searching for multiple criteria that do not rely on a single sort order, linear search may be the only option.
当数据未排序且无法排序（例如，必须保留原始顺序），或列表非常小时，选择线性搜索。此外，如果你要搜索不依赖于单一排序顺序的多个条件，线性搜索可能是唯一的选择。
Use binary search when you have a large, sorted dataset and you need to perform many searches. The initial sorting cost can be amortized over numerous efficient lookups. OCR exam questions often present a sorted list and ask you to demonstrate binary search step by step.
当你有一个大型且已排序的数据集，并且需要执行多次搜索时，使用二分搜索。初始的排序成本可以通过大量高效查找来分摊。OCR 考试题目经常会给出一个已排序的列表，并要求你逐步演示二分搜索。
10. Search Algorithms in Pseudocode and Implementation | 搜索算法的伪代码与实现
In the OCR exam, you may be required to trace a search algorithm on a given array, write pseudocode from memory, or identify errors in a provided implementation. Practice comparing values with A[mid], updating low and high pointers, and correctly handling the exit condition.
在 OCR 考试中，你可能需要针对给定数组跟踪搜索算法的执行过程，凭记忆编写伪代码，或找出给定实现中的错误。练习比较 A[mid] 的值，更新 low 和 high 指针，并正确处理退出条件。
Common implementation mistakes include using A[mid] > T instead of A[mid] < T when updating high, forgetting to add or subtract 1 from mid, or using the wrong loop condition (low < high versus low ≤ high).
常见的实现错误包括：在更新 high 时误用 A[mid] > T 而非 A[mid] < T，忘记对 mid 执行加 1 或减 1，或者使用了错误的循环条件（low < high 与 low ≤ high 混淆）。
11. Exam Tips and Common Mistakes | 考试技巧与常见错误
Tip 1: State the precondition. Always mention that binary search requires the array to be sorted. Many marks are lost by simply providing the algorithm without clarifying this crucial assumption.
建议 1：说明前提条件。务必提到二分搜索要求数组已排序。许多考生只提供算法而未能阐明这一关键假设，从而失分。
Tip 2: Count comparisons precisely. When an exam question asks for the number of comparisons, include the final comparison that confirms the target, even if it is successful. In binary search, each iteration involves one comparison with the middle element (and possible comparisons in the IF conditions).
建议 2：精确计算比较次数。当考题要求计算比较次数时，要包含确认目标的最后一次比较，即使它成功了。在二分搜索中，每次迭代包含一次与中间元素的比较（以及 IF 条件中可能的比较）。
Tip 3: Handle the ‘not found’ case. Ensure your pseudocode returns a sentinel value (like -1) or a Boolean false when the target is absent. OCR mark schemes often allocate marks for this outcome.
建议 3：处理“未找到”情况。确保你的伪代码在目标不存在时返回一个标志值（如 -1）或布尔值 false。OCR 的评分方案通常会为这一结果分配分数。
Tip 4: Practice trace tables. For binary search, maintain a table showing low, high, mid, A[mid], and the logic branch taken. This helps you avoid off-by-one errors.
建议 4：练习跟踪表。对于二分搜索，维护一个显示 low、high、mid、A[mid] 以及所执行逻辑分支的表格。这有助于你避免“差一”错误。
12. Summary and Key Takeaways | 总结与关键要点
Linear search is a brute-force algorithm with O(n) complexity, suitable for any data order but inefficient for large lists. Binary search delivers O(log n) performance but strictly demands sorted data. Understanding the trade-offs, being able to write and trace both algorithms, and recalling their Big O characteristics are essential for success in the OCR A-Level Computer Science exam.
线性搜索是一种复杂度为 O(n) 的蛮力算法，适用于任何数据排列顺序，但对于大型列表效率低下。二分搜索提供 O(log n) 的性能，但严格要求已排序的数据。理解这些权衡、能够编写和跟踪这两种算法，并记住它们的大 O 特性，对于在 OCR A-Level 计算机科学考试中取得成功至关重要。
Regularly practicing past paper questions on searching, including those that interleave searching with sorting concepts, will reinforce your confidence and accuracy under time pressure.
定期练习关于搜索的历年真题，包括那些将搜索与排序概念交织在一起的题目，将增强你在时间压力下的信心和准确性。
Published by TutorHao | Computing Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply