IGCSE CIE Computer Science: Search Algorithms Deep Dive | IGCSE CIE 计算机：搜索算法考点精讲

📚 IGCSE CIE Computer Science: Search Algorithms Deep Dive | IGCSE CIE 计算机：搜索算法考点精讲

Searching is a fundamental operation in computer science that allows us to locate specific data items within a collection. For the Cambridge IGCSE Computer Science syllabus (0478), you are expected to understand how linear search and binary search work, write pseudocode for each algorithm, analyse their efficiency, and know when to apply them. This article breaks down all the key concepts, step-by-step processes, and typical exam questions you will encounter.

搜索是计算机科学中一项基础操作，用于在数据集合中定位特定的数据项。根据剑桥 IGCSE 计算机科学大纲（0478），你需要掌握线性搜索和二分搜索的工作原理，能够为每种算法编写伪代码，分析它们的效率，并知道何时使用它们。本文将拆解所有关键概念、分步流程以及你将会遇到的典型考题。

1. What is a Search Algorithm? | 什么是搜索算法？

A search algorithm is a method for finding a particular item in a dataset. It takes a list (or array) of elements and a target value as input, and returns either the position of the target item or a message indicating that the item is not present. In the IGCSE syllabus, we focus on two essential search algorithms: linear search and binary search.

搜索算法是一种在数据集中查找特定元素的方法。它接收一个元素列表（或数组）以及一个目标值作为输入，返回目标项的位置或指示未找到该项目的消息。在 IGCSE 大纲中，我们重点关注两种基本搜索算法：线性搜索和二分搜索。

Understanding search algorithms is crucial because they form the basis of many real-world applications, from finding a contact in your phone book to retrieving a record from a database. The choice of algorithm depends on whether the data is sorted and how many items need to be checked.

理解搜索算法至关重要，因为它们是许多实际应用的基础——从在通讯录中查找联系人到从数据库中检索记录。选择哪种算法取决于数据是否已排序以及需要检查多少项。

2. Linear Search: Step-by-Step Process | 线性搜索：逐步流程

Linear search, also called sequential search, examines each element in a list one by one, from the first element to the last, until it either finds the target value or reaches the end of the list without a match. It works on both sorted and unsorted data.

线性搜索，也称顺序搜索，从第一个元素到最后一个元素逐一检查列表中的每一项，直到找到目标值或者遍历完整张列表仍未找到匹配项。它适用于已排序和未排序的数据。

The algorithm is straightforward:

Start at index 0.
Compare the current element with the target value.
If they match, return the current index.
If they do not match, move to the next index and repeat.
If the end of the list is reached without a match, return an indicator such as -1 or the message “not found”.

该算法非常直观：

从索引 0 开始。
将当前元素与目标值进行比较。
若匹配，返回当前索引。
若不匹配，移动到下一个索引并重复。
如果到达列表末尾仍未找到匹配项，返回一个指示符，如 -1 或“未找到”的消息。

For example, searching for the number 7 in the list [3, 1, 9, 7, 4] would involve checking 3, then 1, then 9, and finally finding a match at index 3.

例如，在列表 [3, 1, 9, 7, 4] 中搜索数字 7 时，会依次检查 3，然后是 1，接着是 9，最后在索引 3 处找到匹配项。

3. Linear Search Pseudocode and Tracing | 线性搜索伪代码与追踪

Examiners often ask candidates to write pseudocode for linear search or to trace the execution of the algorithm on a given array. Here is a typical pseudocode representation that uses an array and a WHILE loop:

考官经常要求考生编写线性搜索的伪代码，或在给定数组上追踪算法的执行过程。以下是使用数组和 WHILE 循环的典型伪代码表示：

INPUT target
index ← 0
found ← FALSE
WHILE index < LENGTH(array) AND found = FALSE
    IF array[index] = target THEN
        found ← TRUE
    ELSE
        index ← index + 1
    ENDIF
ENDWHILE
IF found = TRUE THEN
    OUTPUT index
ELSE
    OUTPUT “Not found”
ENDIF

When tracing this pseudocode, you would keep track of the values of index, found, and the array element at the current index. This shows the examiner you understand exactly how the algorithm steps through the list.

在追踪这段伪代码时，你需要记录 index、found 以及当前索引对应数组元素的值。这向考官展示了你完全理解算法是如何一步步遍历列表的。

4. Efficiency of Linear Search | 线性搜索的效率

The performance of a linear search can be measured by the number of comparisons made. In the worst-case scenario, the target is either at the very end of the list or not present at all, requiring the algorithm to check every single element. For a list of n items, the maximum number of comparisons is n.

线性搜索的性能可以通过进行比较的次数来衡量。在最坏情况下，目标要么在列表的最末尾，要么根本不在列表中，算法需要检查每一个元素。对于包含 n 个元素的列表，最大比较次数为 n。

This makes linear search an O(n) algorithm, where the time taken grows linearly with the size of the input. While it is simple to implement and requires no sorting, it becomes slow when the dataset is very large. In an exam, you may be asked to compare its efficiency with binary search and to recommend when to use each one.

这使得线性搜索成为一种 O(n) 算法，即所需时间随输入规模线性增长。虽然它实现简单且无需排序，但当数据集非常大时就会变得很慢。在考试中，你可能会被要求将其效率与二分搜索进行比较，并建议何时使用每一种算法。

5. Introduction to Binary Search | 二分搜索简介

Binary search is a much faster algorithm, but it has a strict requirement: the data must be sorted in ascending (or descending) order. Instead of checking each element sequentially, binary search repeatedly divides the search interval in half, discarding the half that cannot contain the target value.

二分搜索是一种速度快得多的算法，但它有一个严格的要求：数据必须按升序（或降序）排列。二分搜索不是依次检查每个元素，而是反复将搜索区间一分为二，舍弃不可能包含目标值的那一半。

Think of looking up a word in a dictionary. You open the book near the middle, and depending on whether your word comes before or after that page, you discard the other half of the book. You repeat this halving process until you find the word. Binary search works exactly on this principle.

想象一下在字典中查找一个单词。你翻开字典靠近中间的位置，根据你的单词在该页之前还是之后，舍弃字典的另一半。你重复这个折半过程，直到找到单词。二分搜索正是基于这一原理工作的。

6. Binary Search Algorithm Step-by-Step | 二分搜索算法逐步详解

The binary search algorithm maintains two pointers (or indices): low, initially set to 0, and high, initially set to the last index of the array. It then calculates a mid index and compares the element at that position with the target.

二分搜索算法维护两个指针（或索引）：low 初始设为 0，high 初始设为数组的最后一个索引。然后计算 mid 索引，并将该位置的元素与目标值进行比较。

The complete steps are as follows:

Set low = 0, high = (length of array) – 1, found = FALSE.
WHILE low ≤ high AND found = FALSE:
mid ← (low + high) DIV 2 (integer division).
IF array[mid] = target THEN found ← TRUE.
ELSE IF array[mid] < target THEN low ← mid + 1.
ELSE high ← mid – 1.
ENDWHILE
If found is TRUE, output mid; otherwise output “not found”.

完整的步骤如下：

设置 low = 0，high =（数组长度）- 1，found = FALSE。
当 low ≤ high 且 found = FALSE 时：
mid ← (low + high) DIV 2（整数除法）。
如果 array[mid] = target，则 found ← TRUE。
否则如果 array[mid] < target，则 low ← mid + 1。
否则 high ← mid – 1。
结束循环
若 found 为 TRUE，输出 mid；否则输出“未找到”。

7. Tracing a Binary Search | 追踪二分搜索

Exam questions frequently present a sorted list and ask you to perform a binary search for a specific value, showing the values of low, high and mid at each step. For example, search for 23 in the sorted array [2, 5, 9, 14, 18, 23, 31, 42, 55].

考试中经常给出一个已排序列表，要求你对特定值执行二分搜索，并展示每一步 low、high 和 mid 的值。例如，在已排序数组 [2, 5, 9, 14, 18, 23, 31, 42, 55] 中搜索 23。

You would start with low = 0, high = 8 (since there are 9 elements, index 0 to 8). The first mid is (0+8) DIV 2 = 4. array[4] is 18, which is less than 23, so you discard the left half and set low = mid + 1 = 5. Now low = 5, high = 8. Next mid = (5+8) DIV 2 = 6. array[6] is 31, which is greater than 23, so high = mid – 1 = 5. Finally low = 5, high = 5, mid = 5. array[5] = 23, found at index 5. This illustrates the halving property clearly.

你会从 low = 0，high = 8 开始（因为有 9 个元素，索引从 0 到 8）。第一个 mid 为 (0+8) DIV 2 = 4。array[4] 是 18，小于 23，因此舍弃左半部分，设 low = mid + 1 = 5。现在 low = 5，high = 8。下一个 mid = (5+8) DIV 2 = 6。array[6] 是 31，大于 23，所以 high = mid – 1 = 5。最后 low = 5，high = 5，mid = 5。array[5] = 23，在索引 5 找到。这清楚地展示了折半特性。

8. Efficiency and Time Complexity of Binary Search | 二分搜索的效率与时间复杂度

Binary search is vastly more efficient than linear search on large sorted datasets. Each comparison halves the remaining search space. The maximum number of comparisons needed is approximately log₂(n), where n is the number of items. For example, for a list of 1 000 000 items, linear search might need up to 1 000 000 comparisons, while binary search needs at most about 20.

对于大型已排序数据集，二分搜索比线性搜索高效得多。每次比较都会将剩余的搜索空间减半。所需的最大比较次数大约为 log₂(n)，其中 n 为元素个数。例如，对于包含 1 000 000 个元素的列表，线性搜索最多可能需要 1 000 000 次比较，而二分搜索最多只需大约 20 次。

The time complexity of binary search is O(log n), which is a logarithmic growth rate. This makes it extremely scalable. However, the cost is the need to keep the data sorted, and sorting itself can take significant time. This is an important trade-off discussed in the IGCSE syllabus.

二分搜索的时间复杂度为 O(log n)，呈对数增长率。这使得它的可扩展性极强。然而，代价是需要保持数据有序，而排序本身可能耗费大量时间。这是 IGCSE 大纲中讨论的一个重要权衡问题。

9. Requirements and Limitations of Binary Search | 二分搜索的要求与局限性

For binary search to work correctly, the list must be sorted. If the list is not in order, the halving logic breaks down and the algorithm may fail to find an item that is actually present. Additionally, binary search typically requires random access to elements, which means it works best with arrays rather than linked lists where direct index access is not possible.

为了让二分搜索正确工作，列表必须已排序。如果列表无序，折半逻辑就会失效，算法可能找不到实际存在的元素。此外，二分搜索通常需要随机访问元素，这意味着它最适合用于数组，而不适合无法直接通过索引访问的链表。

Another limitation is that binary search only finds the position of one occurrence of a value. If there are duplicates, it may not return the first or the last occurrence without modification. In IGCSE, the simple version returning any matching index is sufficient. You should also be aware that binary search requires integer division and careful updating of pointers to avoid infinite loops.

另一个局限性是二分搜索只能找到一个值出现的一个位置。如果存在重复值，在不做修改的情况下，它可能无法返回第一次或最后一次出现的位置。在 IGCSE 中，返回任意匹配索引的简单版本已经足够。你还应该知道二分搜索需要使用整数除法，并谨慎更新指针以避免无限循环。

10. Linear Search vs Binary Search Comparison | 线性搜索与二分搜索比较

A classic exam question asks you to compare linear search and binary search across several criteria. Here is a summary table:

经典的考题要求你从几个方面比较线性搜索和二分搜索。下表为总结：

Criterion 标准	Linear Search 线性搜索	Binary Search 二分搜索
Data requirement 数据要求	Works on unsorted data	Data must be sorted
Worst-case comparisons 最坏情况比较次数	n	≈ log₂(n)
Time complexity 时间复杂度	O(n)	O(log n)
Implementation ease 实现难易度	Very simple	Slightly more complex, needs careful index handling
Best for 最适合	Small datasets or unsorted data	Large sorted datasets

Understanding this trade-off is essential for scoring high marks on evaluation and justification questions. When asked to choose an algorithm, you must refer to whether the data is already sorted and the size of the dataset.

理解这种权衡对于在评估和论证题中取得高分至关重要。当被问到选择哪种算法时，你必须提到数据是否已排序以及数据集的大小。

11. Common Exam Pitfalls and Tips | 常见考试误区与技巧

Many students lose marks by writing pseudocode that contains infinite loops or by incorrectly updating the low and high pointers in binary search. Remember that when array[mid] is less than the target, low becomes mid + 1, not mid. When it is greater, high becomes mid – 1. Forgetting the +1 and -1 can cause the loop to never end.

许多学生因为所写的伪代码包含无限循环，或者在二分搜索中错误地更新 low 和 high 指针而丢分。记住，当 array[mid] 小于目标值时，low 变为 mid + 1，而不是 mid。当大于目标值时，high 变为 mid – 1。忘记 +1 和 -1 可能导致循环永不结束。

Another common error is not using integer division for calculating the mid index. In pseudocode, you should always use DIV or explicitly state integer division. Also, ensure your condition for continuing the search is low ≤ high, because low and high may become equal when the search interval contains only one element.

另一个常见错误是在计算 mid 索引时不使用整数除法。在伪代码中，你应该始终使用 DIV 或明确说明是整数除法。此外，要确保继续搜索的条件是 low ≤ high，因为当搜索区间仅剩一个元素时，low 和 high 可能会相等。

12. Practice Questions and Summary | 练习题与总结

To master search algorithms for your IGCSE Computer Science exam, practice writing pseudocode from memory and tracing both algorithms on provided arrays. Consider questions like: “State one advantage of a linear search over a binary search.” A model answer: A linear search can be used on unsorted data, whereas a binary search requires the data to be sorted first.

为了在 IGCSE 计算机科学考试中掌握搜索算法，请练习从记忆中编写伪代码，并在提供的数组上追踪这两种算法。思考诸如“陈述线性搜索相比二分搜索的一个优点”之类的问题。参考答案：线性搜索可用于未排序的数据，而二分搜索需要先对数据进行排序。

Searching algorithms are a core topic that often appear alongside sorting algorithms in the exam. By understanding the logic, efficiency, and practical constraints of linear and binary search, you will be well-prepared to answer any question that comes your way.

搜索算法是核心主题，在考试中常与排序算法一起出现。通过理解线性搜索和二分搜索的逻辑、效率及实际限制，你将做好充分准备以应对任何相关问题。

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

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

IGCSE CIE Computer Science: Search Algorithms Deep Dive | IGCSE CIE 计算机：搜索算法考点精讲