Searching Algorithms: Linear and Binary Search | IGCSE OCR 计算机：搜索算法考点精讲

📚 Searching Algorithms: Linear and Binary Search | IGCSE OCR 计算机：搜索算法考点精讲

Searching algorithms are fundamental to computer science, enabling programs to locate specific data items within a dataset. In the IGCSE OCR specification, you need to understand two core search methods: linear search and binary search. This article explains how each algorithm works, compares their efficiency, and covers exam-style questions to help you master the topic.

搜索算法是计算机科学的基础，使程序能够在数据集中定位特定的数据项。在 IGCSE OCR 考纲中，你需要掌握两种核心搜索方法：线性搜索和二分搜索。本文将解释每种算法的工作原理，比较它们的效率，并涵盖考试题型，帮助你掌握这一主题。

1. Introduction to Searching Algorithms | 搜索算法简介

A searching algorithm is a step-by-step procedure used to find a target value within a collection of data. The choice of algorithm depends on the structure of the data and its size. We focus on linear search (serial search) and binary search, which are commonly examined.

搜索算法是一种用于在数据集合中查找目标值的逐步过程。算法的选择取决于数据的结构和规模。我们重点讨论线性搜索（顺序搜索）和二分搜索，这些是考试中常见的内容。

2. Linear Search: How It Works | 线性搜索的工作原理

Linear search checks each element of a list one by one, from the first item to the last, until the target value is found or the list ends. It does not require the data to be sorted, making it simple but often slow for large datasets.

线性搜索逐个检查列表中的每个元素，从第一项到最后一项，直到找到目标值或列表结束。它不要求数据已排序，因此简单易懂，但对于大型数据集通常较慢。

3. Linear Search: Example and Pseudocode | 线性搜索示例与伪代码

Suppose we have an array [5, 8, 2, 10, 3] and we search for 10. The algorithm starts at index 0 (value 5), moves to index 1 (8), index 2 (2), and finds 10 at index 3, stopping there. Below is the standard pseudocode:

假设我们有一个数组 [5, 8, 2, 10, 3]，要搜索 10。算法从索引 0（值 5）开始，移动到索引 1（8），索引 2（2），在索引 3 找到 10，停止。以下是标准伪代码：


FUNCTION linearSearch(list, target)
  FOR i ← 0 TO LENGTH(list)-1
    IF list[i] = target THEN
      RETURN i
    ENDIF
  NEXT i
  RETURN -1
ENDFUNCTION

The loop iterates through each position, and returns the index when a match occurs. If no match is found, it returns -1 to indicate failure.

循环遍历每个位置，匹配时返回索引。如果没有找到匹配项，返回 -1 表示失败。

4. Linear Search: Performance and Efficiency | 线性搜索的性能与效率

In the worst case, linear search must examine every element, requiring n comparisons for a list of size n. Its time complexity is O(n). Best case is O(1) when the target is the first element. This algorithm is inefficient for large sorted data but works on any list.

在最坏情况下，线性搜索必须检查每个元素，对于大小为 n 的列表需要 n 次比较。时间复杂度为 O(n)。最好情况是目标为第一个元素，O(1)。该算法对大型有序数据效率低下，但适用于任何列表。

5. Binary Search: Prerequisites and Concept | 二分搜索的前提与概念

Binary search is a much faster algorithm but requires the data to be sorted in ascending (or descending) order. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the lower half; otherwise, it continues in the upper half.

二分搜索是一种快得多的算法，但要求数据按升序（或降序）排序。它通过反复将搜索区间减半来工作。如果目标值小于中间元素，则在下半部分继续搜索；否则在上半部分继续。

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

Given a sorted list, set two pointers: low (first index) and high (last index). While low ≤ high:

给定一个有序列表，设置两个指针：low（第一个索引）和 high（最后一个索引）。当 low ≤ high 时：

1. Calculate mid = (low + high) DIV 2 (integer division).

2. If list[mid] equals the target, return mid.

3. If target < list[mid], set high = mid - 1.

4. If target > list[mid], set low = mid + 1.

If the loop ends, the target is not in the list.

1. 计算 mid = (low + high) DIV 2（整数除法）。

2. 如果 list[mid] 等于目标，返回 mid。

3. 如果目标 < list[mid]，设 high = mid - 1。

4. 如果目标 > list[mid]，设 low = mid + 1。

如果循环结束，目标不在列表中。

7. Binary Search: Example and Pseudocode | 二分搜索示例与伪代码

Sorted list: [2, 3, 5, 7, 11, 13, 17], target = 13. Steps: low=0, high=6, mid=3 (value 7), 13>7 → low=4. New mid=5 (value 13), match found. Pseudocode:

有序列表：[2, 3, 5, 7, 11, 13, 17]，目标 = 13。步骤：low=0, high=6, mid=3（值 7），13>7 → low=4。新 mid=5（值 13），找到匹配。伪代码：


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

8. Binary Search: Performance and Efficiency | 二分搜索的性能与效率

Binary search halves the search space each time, giving a worst-case time complexity of O(log n). For a list of 1,000,000 items, it only needs about 20 comparisons. However, the data must be sorted beforehand, which adds an initial cost.

二分搜索每次将搜索空间减半，最坏情况时间复杂度为 O(log n)。对于一个包含 1,000,000 项的列表，仅需约 20 次比较。然而，数据必须预先排序，这增加了初始成本。

9. Comparison of Linear and Binary Search | 线性与二分搜索的比较

Feature	Linear Search	Binary Search
Data requirement	Unsorted or sorted	Must be sorted
Worst-case time	O(n)	O(log n)
Implementation	Very simple	More complex
Best for	Small lists or frequent changes	Large, static sorted lists

特征比较表如上。线性搜索简单灵活，但速度慢；二分搜索速度极快，但依赖排序。

10. Choosing the Right Search Algorithm | 选择合适的搜索算法

When deciding which algorithm to use, consider: is the data sorted? How large is the dataset? Will the data change often? If the data is unsorted or small, linear search is acceptable. If the data is already sorted and large, binary search is far superior.

在选择算法时，请考虑：数据是否已排序？数据集有多大？数据会频繁变动吗？如果数据未排序或规模较小，线性搜索可以接受。如果数据已排序且较大，二分搜索则远远优于线性搜索。

Additionally, if the list is frequently updated, maintaining sort order for binary search may be costly. In such cases, linear search might be the pragmatic choice.

此外，如果列表频繁更新，为二分搜索维持排序状态可能代价高昂。在这种情况下，线性搜索可能是更务实的选择。

11. Common Exam Questions and Tips | 常见考题与技巧

OCR IGCSE exams often ask you to trace the steps of both algorithms on a given list. Show the values of pointers (low, high, mid) clearly. You may be asked to write pseudocode, explain time complexity, or identify the number of comparisons in a specific scenario.

OCR IGCSE 考试经常要求你追踪给定列表上两种算法的步骤。要清楚地显示指针（low, high, mid）的值。你可能会被要求编写伪代码、解释时间复杂度，或确定特定情境下的比较次数。

Tip: remember that binary search only works on sorted arrays. If the question does not state the list is sorted, you must mention that sorting is required first, or use linear search.

提示：记住二分搜索只适用于有序数组。如果题目未说明列表已排序，你必须指出需要先排序，或者使用线性搜索。

12. Summary | 总结

Linear search examines items sequentially; it is simple but inefficient for large n. Binary search repeatedly halves the search area on sorted data, achieving logarithmic time. Understanding these algorithms, their pseudocode, and performance characteristics will prepare you for OCR exam success.

线性搜索按顺序检查项目；简单但对大数据量效率低。二分搜索在有序数据上反复将搜索区域减半，实现对数时间。理解这些算法、其伪代码和性能特征，将助你在 OCR 考试中取得成功。

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

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

Searching Algorithms: Linear and Binary Search | IGCSE OCR 计算机：搜索算法考点精讲