📚 Linear and Binary Search | 线性搜索与二分搜索考点精讲
Search algorithms are essential tools in computer science – they help programs locate specific items within data collections quickly and reliably. In the OCR GCSE specification, you need to understand how linear search and binary search work, their efficiency, and when to use each one. This revision guide breaks down every concept you must master for the exam.
搜索算法是计算机科学中的核心工具，它能帮助程序快速、可靠地在数据集合中定位特定元素。在 OCR GCSE 考试规范中，你需要理解线性搜索和二分搜索的工作原理、效率以及各自的使用场景。这份考点精讲将为你逐一拆解必须掌握的所有概念。
1. What Is a Search Algorithm? | 什么是搜索算法？
A search algorithm accepts a collection of data items and a target value, then returns the position (or index) of the target if it exists, or an indication that the target is absent. The two foundational search methods covered at GCSE are linear search and binary search.
搜索算法接收一个数据集合和一个目标值，如果目标存在则返回其位置（或索引），否则返回一个表示未找到的标识。GCSE 阶段涵盖的两种基本搜索方法是线性搜索和二分搜索。
2. How Linear Search Works | 线性搜索的工作原理
Linear search examines each element of a list one by one, starting from the first index. It compares every element with the target value until a match is found or the end of the list is reached. This method requires no ordering of the data.
线性搜索从第一个索引开始，逐个检查列表中的每个元素。它将每个元素与目标值进行比较，直到找到匹配项或到达列表末尾。这种方法不需要对数据排序。
Because linear search walks through the entire structure step by step, it is often described as a sequential search. If the target appears multiple times, a linear search can be designed to return the first occurrence or to list all occurrences.
由于线性搜索一步一步地遍历整个数据结构，它常被称作顺序搜索。如果目标值多次出现，线性搜索可以被设计为返回第一次出现的位置，或者列出所有出现的位置。
3. Linear Search Step-by-Step Example | 线性搜索分步示例
Consider the list: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] and target = 23. The algorithm compares index 0 (2) – no match, index 1 (5) – no match, index 2 (8) – no match, index 3 (12) – no match, index 4 (16) – no match, index 5 (23) – match! It returns position 5 and stops.
以列表 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 和目标值 23 为例。算法比较索引 0（2）– 不匹配，索引 1（5）– 不匹配，索引 2（8）– 不匹配，索引 3（12）– 不匹配，索引 4（16）– 不匹配，索引 5（23）– 匹配！它返回位置 5 并停止。
If the target were 99, the search would compare all 10 elements, find no match, and return a ‘not found’ signal (often -1 or a message). This demonstrates the worst-case scenario.
如果目标值为 99，搜索将比较全部 10 个元素，没有匹配项，然后返回“未找到”信号（通常为 -1 或一条消息）。这展示了最坏情况。
4. Performance of Linear Search | 线性搜索的性能分析
In the worst case, linear search must check every element, so the number of comparisons grows in proportion to the list size n. We describe this efficiency using Big O notation: O(n). The best case is O(1) when the target is at the very first position.
在最坏情况下，线性搜索必须检查每一个元素，因此比较次数与列表大小 n 成正比。我们用大 O 符号描述这种效率：O(n)。最佳情况是目标值恰好在第一个位置，此时为 O(1)。
On average, for a random target present in the list, roughly n/2 comparisons are needed. This linear relationship means that doubling the list size roughly doubles the search time.
平均而言，如果目标值随机出现在列表中，大约需要 n/2 次比较。这种线性关系意味着列表长度加倍，搜索时间也大约加倍。
5. How Binary Search Works | 二分搜索的工作原理
Binary search works on a sorted list by repeatedly dividing the search interval in half. It compares the target with the middle element. If they match, the search succeeds. If the target is smaller, the algorithm discards the upper half; if larger, it discards the lower half. This halving continues until the element is found or the interval becomes empty.
二分搜索作用于已排序的列表，通过不断将搜索区间减半来工作。它将目标值与中间元素比较。如果匹配，搜索成功。如果目标值更小，算法丢弃上半部分；如果更大，则丢弃下半部分。这种折半过程持续进行，直到找到元素或区间变空。
Because binary search eliminates half of the remaining data with every comparison, it reaches the target very quickly – provided the list is already ordered.
由于二分搜索每次比较都能排除剩余数据的一半，因此它能极快地找到目标——前提是列表事先已经排序。
6. Preconditions for Binary Search | 二分搜索的前提条件
The most critical requirement is that the data must be sorted in ascending (or descending) order. Without a sorted list, the midpoint logic fails completely. Additionally, binary search requires random access capability, meaning it is naturally suited to arrays rather than linked lists.
最关键的要求是数据必须按升序（或降序）排列。如果没有排序的列表，中间点逻辑将完全失效。此外，二分搜索需要随机访问能力，这意味着它天生适合数组而非链表。
At GCSE level, you can assume the data is stored in an indexable structure. When writing algorithms, you should note that the list must be sorted before applying binary search.
在 GCSE 阶段，你可以假设数据存储在一个可索引的结构中。在编写算法时，你应该注明应用二分搜索前列表必须已排序。
7. Binary Search Step-by-Step Example | 二分搜索分步示例
Using the same sorted list [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] and target 23. Initial low = 0, high = 9. Mid = (0+9)//2 = 4 (element 16). 23 > 16, so low becomes 5. New mid = (5+9)//2 = 7 (element 45). 23 < 45, so high becomes 6. Next mid = (5+6)//2 = 5 (element 23) – match! Only three comparisons were needed.
使用相同的排序列表 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 和目标值 23。初始 low = 0，high = 9。中点 = (0+9)//2 = 4（元素 16）。23 > 16，因此 low 变为 5。新中点 = (5+9)//2 = 7（元素 45）。23 < 45，因此 high 变为 6。下一个中点 = (5+6)//2 = 5（元素 23）——匹配！仅需要三次比较。
If the target were 99, the search would narrow until the low pointer overtakes the high pointer, signalling that the element is not present. This typically takes at most ⌈log₂(n+1)⌉ comparisons.
如果目标值为 99，搜索将不断缩小区间，直到 low 指针超过 high 指针，表示元素不存在。这一过程最多需要 ⌈log₂(n+1)⌉ 次比较。
8. Performance of Binary Search | 二分搜索的性能分析
The efficiency of binary search is logarithmic – O(log₂ n), often simplified to O(log n). Each comparison cuts the problem size roughly in half. For a list of 1,000 elements, binary search finds the target in at most 10 comparisons, while linear search might need up to 1,000.
二分搜索的效率是对数级的——O(log₂ n)，通常简写为 O(log n)。每次比较都会将问题规模大致减半。对于一个包含 1,000 个元素的列表，二分搜索最多需要 10 次比较，而线性搜索可能需要多达 1,000 次。
However, this speed advantage only pays off when the list is already sorted. If sorting is required before searching, the overall cost must be considered – sorting often takes O(n log n) time.
然而，这种速度优势只有在列表已经排序时才能体现。如果搜索前需要排序，则必须考虑整体成本——排序通常需要 O(n log n) 的时间。
9. Comparing Linear and Binary Search | 线性搜索与二分搜索的比较
Linear search is simple to implement and works on any list, sorted or unsorted. Its worst-case time is O(n). Binary search is far more efficient for large, sorted datasets, with O(log n) time, but it fails completely on unsorted data and demands random access.
线性搜索实现简单，适用于任何列表，无论是否排序。其最坏情况时间复杂度为 O(n)。二分搜索对于大型、已排序的数据集效率高得多，时间复杂度为 O(log n)，但它完全不能用于未排序的数据，并且要求随机访问。
Another subtle difference: linear search can handle data that changes rapidly because it does not require sorting; binary search can become costly if the list must be re-sorted after every insertion.
另一个细微的差别：线性搜索可以处理快速变化的数据，因为它不需要排序；而如果每次插入后都需要重新排序，二分搜索的总体成本会变高。
In the exam, you may be asked to state which algorithm uses fewer comparisons for a given scenario. Remember the key trade-off: binary search gains speed on sorted data, while linear search trades speed for simplicity and unsorted-data compatibility.
在考试中，你可能会被要求说明在特定场景下哪种算法使用的比较次数更少。记住关键的权衡：二分搜索以排序为前提换取速度，而线性搜索则牺牲速度换取简单性和对未排序数据的兼容性。
10. Choosing the Right Search Algorithm | 搜索算法的选择
Choose linear search when the list is unsorted, the dataset is very small, or your program cannot guarantee sorted order. It is also appropriate when the data structure does not support random access (e.g., a linked list).
当列表未排序、数据集非常小，或者程序无法保证排序顺序时，选择线性搜索。当数据结构不支持随机访问（如链表）时，它也是合适的选择。
Choose binary search when you have a large, sorted array and you need to perform many searches. The initial cost of sorting can be justified by the huge reduction in subsequent search times. Many built-in searching functions in programming languages assume sorted data and use binary search or its variants.
当你有一个大型的已排序数组，并且需要执行大量搜索时，选择二分搜索。排序的初始成本可以通过后续搜索时间的大幅降低来弥补。编程语言中的许多内置搜索函数假设数据已排序，并使用二分搜索或其变体。
11. Common Misconceptions and Pitfalls | 常见误区与易错点
Many students forget that binary search only works on sorted data. Applying the midpoint divide-and-conquer logic to an unordered list will produce inconsistent, incorrect results. Always check the sorting precondition.
许多学生忘记二分搜索仅适用于已排序的数据。将中点分治逻辑应用于无序列表会产生不一致的、错误的结果。务必检查排序这一前提条件。
Another common error is mishandling the boundaries. When updating low and high, using incorrect indices (e.g., low = mid instead of mid + 1) can cause infinite loops or missed targets. Practise writing out the index updates carefully.
另一个常见错误是边界处理不当。更新 low 和 high 时，若使用了错误的索引（例如 low = mid 而不是 mid + 1），可能导致无限循环或漏掉目标值。请仔细练习编写索引更新步骤。
For linear search, a typical slip‑up is forgetting to stop after finding the target. In the exam, you must be explicit about what the algorithm returns and when it terminates.
对于线性搜索，一个典型的疏忽是在找到目标后忘记停止。在考试中，你必须明确说明算法返回什么以及何时终止。
12. Exam-Style Tips and Summary | 考试技巧与总结
OCR GCSE questions often present a sorted or unsorted list and ask you to trace the search algorithm, stating the number of comparisons. Always show your working – write each comparison step by step, and keep track of low, mid and high pointers for binary search.
OCR GCSE 题目通常会给出一个已排序或未排序的列表，要求你追踪搜索算法，并说明比较次数。务必展示你的计算过程——一步步写出每次比较，并为二分搜索记录低、中、高指针的变化。
Remember: O(n) for linear search, O(log n) for binary search. When comparing algorithms, mention the necessity of sorting, the impact of data size, and the suitability for the underlying data structure. Use clear, concise language and proper Big O notation.
记住：线性搜索 O(n)，二分搜索 O(log n)。比较算法时，要提及排序的必要性、数据规模的影响以及对底层数据结构的适用性。使用清晰、简洁的语言和正确的大 O 符号。
Finally, practise writing simple pseudocode for both searches; the exam may ask you to complete a partially written algorithm or to identify errors in a given implementation.
最后，练习编写两种搜索的简单伪代码；考试可能会要求你补全一个不完整的算法，或找出给定实现中的错误。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导