Searching Algorithms: Linear and Binary Search | 搜索算法：线性搜索与二分搜索

📚 Searching Algorithms: Linear and Binary Search | 搜索算法：线性搜索与二分搜索

Searching is a fundamental operation in computer science that allows us to locate a particular item within a collection of data. Whether we are looking for a contact in a phonebook, a word in a dictionary, or a record in a database, a searching algorithm defines the step-by-step procedure to find the target efficiently. In the CCEA IGCSE Computer Science syllabus, two core searching algorithms are covered: linear search and binary search. Understanding how they work, their pseudocode, and their efficiency is essential for both the written examination and practical programming tasks.

搜索是计算机科学中的一项基本操作，它让我们能够在数据集合中定位特定的项目。无论我们是在电话簿中寻找联系人、在字典中查找单词，还是在数据库中检索记录，搜索算法都定义了逐步找到目标的高效过程。在 CCEA IGCSE 计算机科学课程中，涵盖了两个核心搜索算法：线性搜索和二分搜索。理解它们的工作原理、伪代码以及效率，对笔试和实践编程任务都至关重要。

1. What is Searching? | 什么是搜索？

Searching refers to the process of finding the position of a target value within a data structure, typically an array or list. The algorithm returns the index of the element if found, or a special value (like -1) to indicate that the item is not present. Searching algorithms are categorised by their strategy and performance, and they form the backbone of many higher-level applications such as information retrieval, databases, and artificial intelligence.

搜索是指在数据结构（通常是数组或列表）中找到目标值的位置的过程。如果找到元素，算法会返回其索引；否则返回一个特殊值（比如 -1）表示该项目不存在。搜索算法根据策略和性能进行分类，它们是信息检索、数据库和人工智能等许多高级应用程序的骨干。

---

2. Introduction to Linear Search | 线性搜索简介

Linear search, also known as sequential search, is the simplest searching method. It checks each element of the list one by one, starting from the first index, until the desired element is found or the end of the list is reached. Because it does not rely on any ordering of the data, linear search works on both sorted and unsorted lists.

线性搜索，又称顺序搜索，是最简单的搜索方法。它从第一个索引开始，逐个检查列表中的每个元素，直到找到所需元素或到达列表末尾。由于它不依赖于数据的任何顺序，线性搜索适用于已排序和未排序的列表。

For example, if we have an array [7, 3, 9, 2, 5] and we search for 9, the algorithm will inspect index 0 (7), then index 1 (3), then index 2 (9) and stop, returning 2.

例如，如果我们有一个数组 [7, 3, 9, 2, 5]，搜索 9，算法会检查索引 0（7），然后索引 1（3），然后索引 2（9）并停下，返回 2。

Linear search is often used when the dataset is small or when simplicity is more important than speed. It requires no pre-processing and is very easy to code.

线性搜索通常在数据集较小或简单性比速度更重要时使用。它不需要预处理，并且非常容易编写。

---

3. Linear Search Pseudocode | 线性搜索伪代码

The logic of linear search can be expressed in clear pseudocode. Here is a typical iterative version that searches an array arr of size n for a target value:

线性搜索的逻辑可以用清晰的伪代码表达。下面是一个典型的迭代版本，它在大小为 n 的数组 arr 中搜索 target 值：

FOR i ← 0 TO n-1
IF arr[i] = target THEN
RETURN i
ENDIF
ENDFOR
RETURN -1

In this pseudocode, the variable i serves as the index that moves from 0 to n-1. The IF condition compares the current element with the target. If a match occurs, the index is returned immediately. If the loop finishes without finding the target, the algorithm returns -1 to signal failure.

在这段伪代码中，变量 i 作为索引，从 0 移动到 n-1。IF 条件将当前元素与目标进行比较。如果匹配，立即返回索引。如果循环结束而未找到目标，算法返回 -1 表示失败。

A common exam requirement is to trace this pseudocode using a given list, showing the values of i and the comparisons made at each step.

常见的考试要求是使用给定列表跟踪这段伪代码，显示每一步 i 的值和所进行的比较。

---

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

We evaluate the efficiency of an algorithm by analysing the number of key operations as the input size n grows. For linear search, the dominant operation is the comparison of elements. In the worst case, the target is at the very end of the list or missing entirely, requiring n comparisons. In the best case, the target is the first element, needing only 1 comparison. The average case is n/2 comparisons.

我们通过分析关键操作的数量随输入规模 n 增长的情况来评估算法的效率。对于线性搜索，主导操作是元素的比较。在最坏情况下，目标位于列表末尾或完全不存在，需要 n 次比较。在最好情况下，目标是第一个元素，只需 1 次比较。平均情况是 n/2 次比较。

We express the time complexity of linear search using Big O notation as O(n). This means that the running time grows linearly with the size of the input. Linear search is inefficient for very large datasets because the number of comparisons doubles when the list size doubles.

我们用大 O 表示法表示线性搜索的时间复杂度为 O(n)。这意味着运行时间随输入规模线性增长。对于非常大的数据集，线性搜索效率低下，因为当列表大小翻倍时，比较次数也翻倍。

Despite its linear complexity, linear search remains advantageous for unsorted data and for small arrays, where the overhead of more complex algorithms is not justified.

尽管是线性复杂度，线性搜索在处理未排序数据和小型数组时仍具有优势，因为在这种场景下，处理更复杂算法的开销没有意义。

---

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

Binary search is a much faster algorithm, but it comes with a crucial requirement: the list must be sorted in ascending (or descending) order. It works on the divide-and-conquer principle. The algorithm repeatedly divides the search interval in half, comparing the middle element with the target value. If the target matches the middle element, the search ends. If the target is greater, the search continues in the right half; if smaller, in the left half.

二分搜索是一种快得多的算法，但它有一个关键要求：列表必须按升序（或降序）排序。它采用分治原理工作。算法反复将搜索区间一分为二，将中间元素与目标值进行比较。如果目标与中间元素匹配，搜索结束。如果目标更大，则继续在右半部分搜索；如果更小，则在左半部分搜索。

This halving strategy drastically reduces the number of comparisons needed. For example, in a sorted list of 1,000,000 elements, binary search locates a target in at most about 20 comparisons, whereas linear search could require up to 1,000,000.

这种减半策略极大地减少了所需的比较次数。例如，在一个包含 1,000,000 个元素的排序列表中，二分搜索最多只需大约 20 次比较即可定位目标，而线性搜索可能需要多达 1,000,000 次。

---

6. Preconditions for Binary Search | 二分搜索的前提条件

The most critical rule for binary search is that the data structure must be sorted. If the list is not sorted, the algorithm may discard the wrong half and fail to find the item even if it exists. In many cases, sorting the data first adds an overhead of O(n log n), but once sorted, multiple binary searches can be performed extremely efficiently.

二分搜索最关键的要求是数据结构必须排序。如果列表未排序，算法可能会丢弃错误的半部分，即使项目存在也无法找到。在很多情况下，首先对数据进行排序会产生 O(n log n) 的开销，但一旦排序完成，就可以极其高效地执行多次二分搜索。

Binary search can be applied to any indexed, random-access data structure such as arrays. It is also suitable for data stored in a balanced binary search tree, which inherently supports logarithmic searches, but the array version is the standard GCSE algorithm.

二分搜索适用于任何支持索引、随机访问的数据结构，如数组。它也适合存储在平衡二叉搜索树中的数据，这种树天然支持对数时间的搜索，但数组版本是标准的 GCSE 算法。

Understanding and checking this precondition is a common exam question. Candidates must be able to state why binary search cannot be used on an unsorted list and must identify whether a given dataset is appropriate for its use.

理解并检查这个前提条件是常见的考试问题。考生必须能够说明为什么二分搜索不能用于未排序列表，并判断给定数据集是否适合使用二分搜索。

---

7. Binary Search Pseudocode | 二分搜索伪代码

The following pseudocode demonstrates the iterative binary search algorithm. It maintains two pointers, low and high, that define the current search boundaries, and a variable mid for the middle index.

下面的伪代码演示了迭代式二分搜索算法。它维护两个指针 low 和 high，定义当前搜索边界，以及变量 mid 表示中间索引。

low ← 0
high ← n – 1
WHILE low <= high DO
mid ← (low + high) DIV 2
IF arr[mid] = target THEN
RETURN mid
ELSE IF arr[mid] < target THEN
low ← mid + 1
ELSE
high ← mid – 1
ENDIF
ENDWHILE
RETURN -1

The integer division DIV 2 finds the middle index (in some pseudocode variants, FLOOR division is used). If the element at mid equals the target, the index is returned. If it is smaller, the search moves to the right half by setting low to mid + 1. If it is larger, the search moves to the left half by setting high to mid – 1. The loop stops when low exceeds high, meaning the element is absent.

整数除法 DIV 2 用于找到中间索引（在某些伪代码变体中，使用向下取整除法）。如果 mid 处的元素等于目标，则返回索引。如果它更小，通过将 low 设置为 mid + 1，搜索移至右半部分。如果更大，通过将 high 设置为 mid – 1，搜索移至左半部分。当 low 超过 high 时循环终止，这表示元素不存在。

A very common pitfall is forgetting to update low or high correctly, which can lead to infinite loops. Always ensure the search space shrinks by at least one element in each iteration.

一个非常常见的陷阱是忘记正确更新 low 或 high，这可能导致无限循环。始终确保在每次迭代中，搜索空间至少缩小一个元素。

---

8. Walkthrough Example of Binary Search | 二分搜索示例演练

Let’s apply the algorithm to a concrete sorted array: [2, 5, 7, 9, 12, 16, 20] and search for 12. The initial state sets low = 0, high = 6.

让我们将该算法应用到一个具体的排序数组：[2, 5, 7, 9, 12, 16, 20]，搜索 12。初始状态设置 low = 0, high = 6。

● Iteration 1: mid = (0+6) DIV 2 = 3. arr[3] = 9. Since 9 < 12, we set low = mid + 1 = 4. Search interval now [4, 6].

● 第 1 次迭代：mid = (0+6) DIV 2 = 3。arr[3] = 9。由于 9 < 12，设置 low = mid + 1 = 4。搜索区间现在是 [4, 6]。

● Iteration 2: mid = (4+6) DIV 2 = 5. arr[5] = 16. Now 16 > 12, so we set high = mid – 1 = 4. Search interval [4, 4].

● 第 2 次迭代：mid = (4+6) DIV 2 = 5。arr[5] = 16。现在 16 > 12，因此设置 high = mid – 1 = 4。搜索区间 [4, 4]。

● Iteration 3: mid = (4+4) DIV 2 = 4. arr[4] = 12, which matches the target. The algorithm returns index 4. The search completed in just 3 steps, whereas linear search would have needed 5.

● 第 3 次迭代：mid = (4+4) DIV 2 = 4。arr[4] = 12，匹配目标。算法返回索引 4。搜索仅用 3 步完成，而线性搜索需要 5 步。

This step-by-step trace is a frequent exam requirement. Drawing a table to show the values of low, high, mid, and the comparison result at each pass is highly recommended.

这种逐步跟踪是考试中常见的要求。强烈建议绘制一个表格，显示每一趟 low、high、mid 的值以及比较结果。

---

9. Efficiency and Time Complexity Comparison | 效率与时间复杂度对比

Binary search has a time complexity of O(log n) in the worst case, because each comparison halves the remaining search space. Specifically, the number of comparisons is proportional to log₂ n. For a list of size n, the maximum number of iterations is the smallest integer k such that 2ᵏ ≥ n.

二分搜索在最坏情况下的时间复杂度为 O(log n)，因为每次比较都会将剩余搜索空间减半。具体来说，比较次数与 log₂ n 成正比。对于规模为 n 的列表，最大迭代次数是满足 2ᵏ ≥ n 的最小整数 k。

The table below summarises the key differences between linear and binary search:

下表总结了线性搜索和二分搜索之间的主要区别：

Aspect | 方面	Linear Search | 线性搜索	Binary Search | 二分搜索
Data requirement | 数据要求	Works on unsorted list | 适用于未排序列表	List must be sorted | 列表必须排序
Worst-case complexity | 最坏情况复杂度	O(n)	O(log n)
Best case | 最好情况	O(1) — first element | O(1) – 第一个元素	O(1) — middle element matches | O(1) – 中间元素匹配
Simplicity | 简单性	Very simple to implement | 实现非常简单	More complex, requires careful index handling | 更复杂，需要仔细处理索引
Use case | 使用场景	Small or unsorted datasets | 小型或未排序数据集	Large, sorted datasets with many searches | 大型、已排序、需多次搜索的数据集

It is important to note that for a single search, binary search only outperforms linear search if the list is already sorted. The cost of sorting (O(n log n)) must be considered when evaluating the overall efficiency of a task that includes both sorting and searching.

需要注意的是，对于单次搜索，只有列表已经排序的情况下，二分搜索才优于线性搜索。在评估包含排序和搜索的任务的整体效率时，必须考虑排序的成本（O(n log n)）。

---

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

When deciding which search algorithm to use, consider the state of the data and the frequency of searches:

在决定使用哪种搜索算法时，请考虑数据的状态和搜索频率：

● If the list is small (e.g., fewer than 50 elements), the difference in speed is negligible, and linear search is perfectly acceptable.

● 如果列表较小（例如少于 50 个元素），速度差异可以忽略不计，线性搜索完全可行。

● If the data is unsorted and you only need to search a few times, linear search avoids the cost of sorting.

● 如果数据未排序且只需要搜索几次，线性搜索可避免排序的开销。

● If the data is maintained in sorted order (e.g., a leaderboard) or you will search it many times, sorting once and then using binary search is the optimal strategy.

● 如果数据保持有序（例如排行榜），或者需要多次搜索，则一次性排序后使用二分搜索是最优策略。

● In real-world systems, built-in functions often implement hybrid approaches, but understanding the core algorithms is essential for GCSE.

● 在现实世界的系统中，内置函数通常实现混合方法，但理解核心算法对于 GCSE 至关重要。

---

11. Common Mistakes and Exam Tips | 常见错误与考试技巧

Many students lose marks on searching topics due to avoidable errors. Here are the key points to remember for CCEA IGCSE Computer Science:

许多学生在搜索专题上丢分，原因是一些可避免的错误。以下是为 CCEA IGCSE 计算机科学需要记住的要点：

● Always specify that binary search requires a sorted list. Do not simply say ‘it is faster’ without stating the precondition.

● 务必说明二分搜索需要排序列表。不要只说“它更快”而不提及前提条件。

● In pseudocode, use integer division (DIV or FLOOR) for mid calculation and ensure mid is updated every iteration.

● 在伪代码中，使用整数除法（DIV 或向下取整）计算 mid，并确保每次迭代都更新 mid。

● Avoid infinite loops by correctly setting low = mid + 1 and high = mid – 1; forgetting this is a classic error.

● 通过正确设置 low = mid + 1 和 high = mid – 1 来避免无限循环；忘记这一点是一个经典错误。

● When asked to compare algorithms, support your answer with Big O notation and also mention practical trade-offs like ease of implementation or overhead of keeping the list sorted.

● 当被要求比较算法时，用大 O 表示法来支撑你的答案，同时也要提到实际权衡，比如实现的难易程度或维护列表有序的开销。

● Practise tracing both algorithms on paper with small arrays of 5–8 elements, showing each step clearly, as this is a common exam task.

● 练习在纸上用 5-8 个元素的小数组跟踪两种算法，清晰地显示每一步，因为这是常见的考试任务。

● Be able to convert the pseudocode into a simple program in a high-level language such as Python — CCEA may ask you to write, complete, or debug search code.Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com

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