📚 Search Algorithms in IGCSE WJEC Computer Science | IGCSE WJEC 计算机：搜索 考点精讲
Search algorithms are fundamental techniques in computer science that allow us to locate specific data within a collection. In the IGCSE WJEC Computer Science syllabus, understanding how to search efficiently is a key skill, not only for the examination but also for developing logical thinking and problem-solving abilities. This article will break down the core concepts, pseudocode implementations, and common pitfalls associated with linear search and binary search, helping you achieve top marks.
搜索算法是计算机科学中用来在数据集合中定位特定数据的基础技术。在 IGCSE WJEC 计算机科学教学大纲中，理解如何进行高效搜索是一项关键技能，不仅为了应对考试，更是为了培养逻辑思维和解决问题的能力。本文将详细拆解线性搜索和二分搜索的核心概念、伪代码实现以及常见误区，帮助你获得高分。
1. What is a Search Algorithm? | 什么是搜索算法？
A search algorithm is a step-by-step procedure used to retrieve information stored within some data structure. The goal is to find the position of a target value, or to determine that the value is not present. The efficiency of a search algorithm depends on factors such as the size of the dataset and whether the data is sorted. In WJEC IGCSE, you need to know two primary search methods: linear search and binary search.
搜索算法是一种逐步执行的过程，用于检索存储在某种数据结构中的信息。其目标是找到目标值的位置，或确定该值不存在。搜索算法的效率取决于数据集的大小以及数据是否已排序等因素。在 WJEC IGCSE 课程中，你需要掌握两种主要的搜索方法：线性搜索和二分搜索。
Every search algorithm must be able to handle two outcomes: a successful search (where the item is found) and an unsuccessful search (where the item is not in the list). Understanding this distinction is crucial for writing correct pseudocode and for analysing algorithm performance.
每种搜索算法都必须能够处理两种结果：成功搜索（找到了该项）和不成功搜索（该项不在列表中）。理解这一区别对于编写正确的伪代码和分析算法性能至关重要。
2. Linear Search: The Simple Approach | 线性搜索：简单直接的方法
Linear search, also called sequential search, works by checking each element of the list one by one from the beginning until the target is found or the list ends. It does not require the data to be sorted, which makes it versatile but often slow on large datasets. The algorithm compares the target value with the first element, then the second, and so on.
线性搜索，也称为顺序搜索，通过从头开始逐个检查列表中的每个元素来工作，直到找到目标或列表结束。它不要求数据事先排序，这使它灵活通用，但在大数据集上通常速度较慢。该算法将目标值与第一个元素进行比较，然后是第二个元素，依此类推。
In the best-case scenario, the target is at the very first position, requiring only one comparison. In the worst-case scenario, the target is at the last position or not present at all, requiring comparisons equal to the number of elements, n. Therefore, the maximum number of comparisons for linear search is n. This is an O(n) algorithm.
在最佳情况下，目标就在第一个位置，只需要一次比较。在最坏情况下，目标在最后一个位置或根本不在列表中，需要的比较次数等于元素个数 n。因此，线性搜索的最大比较次数是 n。这是一个 O(n) 算法。
3. Linear Search Pseudocode | 线性搜索伪代码
In the WJEC examination, you may be asked to write or interpret pseudocode for a linear search. The standard logic uses a loop to iterate through the list and an IF statement to check each value. A typical linear search pseudocode looks like this:
在 WJEC 考试中，你可能会被要求编写或解释线性搜索的伪代码。标准逻辑使用循环遍历列表，并用 IF 语句检查每个值。典型的线性搜索伪代码如下：
Pseudocode Example:
PROCEDURE linearSearch(list, target)
FOR index ← 0 TO LENGTH(list)-1
IF list[index] = target THEN
OUTPUT "Found at position ", index
RETURN index
ENDIF
ENDFOR
OUTPUT "Not found"
RETURN -1
ENDPROCEDUREThe algorithm outputs the index of the first occurrence. Notice that if the target is found, the procedure returns immediately; otherwise, after the loop finishes, it reports failure. The returned value -1 is a common convention to indicate an unsuccessful search.
该算法输出第一个出现位置的索引。请注意，如果找到目标，过程会立即返回；否则，在循环结束后，它会报告失败。返回值 -1 是表示搜索不成功的常见约定。
Some questions might ask you to modify the algorithm to count the number of occurrences. In that case, you would not stop after the first match but instead continue through the entire list, incrementing a counter each time the target is found.
有些问题可能要求你修改算法以统计出现次数。在这种情况下，你不会在第一次匹配后就停止，而是继续遍历整个列表，每找到一次目标就将计数器加一。
4. Binary Search: The Divide and Conquer Method | 二分搜索：分治法
Binary search is a much faster algorithm, but it has a strict precondition: the list must be sorted in ascending (or descending) order. It works by repeatedly dividing the search interval in half. The algorithm compares the target value to the middle element of the current interval; if they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half.
二分搜索是一种快得多的算法，但它有一个严格的前提条件：列表必须按升序（或降序）排序。它通过反复将搜索区间减半来工作。算法将目标值与当前区间的中间元素进行比较；如果它们不相等，则剔除目标不可能存在的那个半区，并在剩余的一半上继续搜索。
Because binary search discards half of the remaining elements with each comparison, its maximum number of comparisons is about log₂(n). For a list of 1 000 000 items, linear search might need up to a million checks, whereas binary search requires at most about 20 comparisons. This efficiency makes binary search extremely valuable.
由于二分搜索每比较一次就能舍弃剩余元素的一半，其最大比较次数约为 log₂(n)。对于一个有 1 000 000 个元素的列表，线性搜索可能需要多达一百万次检查，而二分搜索最多只需要大约 20 次比较。这种高效性使二分搜索极具价值。
5. Binary Search Step-by-Step Process | 二分搜索的逐步过程
Let us walk through a binary search example. Suppose we have a sorted list: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] and we are searching for the value 23. The algorithm maintains three pointers: low, high, and mid. Initially, low = 0 and high = 9 (the index of the last element).
让我们详细走一遍二分搜索的示例。假设有一个已排序的列表：[2, 5, 8, 12, 16, 23, 38, 45, 56, 72]，我们正在搜索值 23。该算法维护三个指针：low、high 和 mid。初始时，low = 0，high = 9（最后一个元素的索引）。
Step 1: mid = (0 + 9) DIV 2 = 4 (integer division). The middle element is list[4] = 16. Since 23 > 16, we ignore the left half by setting low = mid + 1, i.e. low = 5.
第 1 步：mid = (0 + 9) DIV 2 = 4（整除）。中间元素是 list[4] = 16。由于 23 > 16，我们忽略左半部分，将 low 设为 mid + 1，即 low = 5。
Step 2: Now low = 5, high = 9. mid = (5 + 9) DIV 2 = 7. list[7] = 45. Since 23 < 45, we ignore the right half by setting high = mid - 1, i.e. high = 6.
第 2 步：现在 low = 5，high = 9。mid = (5 + 9) DIV 2 = 7。list[7] = 45。由于 23 < 45，我们忽略右半部分，将 high 设为 mid - 1，即 high = 6。
Step 3: low = 5, high = 6. mid = (5 + 6) DIV 2 = 5. list[5] = 23. The target is found at index 5! The search ends successfully.
第 3 步：low = 5，high = 6。mid = (5 + 6) DIV 2 = 5。list[5] = 23。目标在索引 5 处找到！搜索成功结束。
If the list had been unsorted, binary search would produce unreliable results. This is a common examination pitfall. Always check that the data is sorted before applying binary search.
如果列表未排序，二分搜索会产生不可靠的结果。这是一个常见的考试陷阱。在应用二分搜索之前，一定要检查数据是否已排序。
6. Binary Search Pseudocode | 二分搜索伪代码
You are expected to understand and be able to reproduce binary search pseudocode for the WJEC IGCSE exam. The standard structure uses a WHILE loop that continues as long as low <= high. Inside the loop, the middle index is calculated, and the appropriate half is selected.
你需要理解并能够为 WJEC IGCSE 考试复现二分搜索的伪代码。标准结构使用一个 WHILE 循环，只要 low <= high 就继续执行。在循环内部，计算中间索引，并选择合适的半区。
Pseudocode for binary search:
PROCEDURE binarySearch(list, target)
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high DO
mid ← (low + high) DIV 2 // integer division
IF list[mid] = target THEN
OUTPUT "Found at position ", mid
RETURN mid
ELSE IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDWHILE
OUTPUT "Not found"
RETURN -1
ENDPROCEDURENote the use of DIV for integer division. In WJEC pseudocode, the keyword DIV indicates that the result is truncated to an integer. Also, the condition list[mid] < target assumes the list is sorted in ascending order. If the list is sorted in descending order, the comparison operator must be reversed.
注意我们使用 DIV 表示整除。在 WJEC 伪代码中，关键字 DIV 表示结果会被截断为整数。同时，条件 list[mid] < target 假设列表是按升序排序的。如果列表是按降序排序的，则比较运算符必须反转。
7. Comparing Linear and Binary Search | 线性搜索与二分搜索的比较
Understanding the differences between these two algorithms is crucial for choosing the right tool for a given situation. The following table summarises the key aspects you need to remember for the exam.
理解这两种算法之间的差异对于在给定情况下选择合适的工具至关重要。下表总结了你需要为考试记住的关键方面。
| Aspect | 方面 | Linear Search | 线性搜索 | Binary Search | 二分搜索 |
|---|---|---|
| Data requirement | 数据要求 | Works on unsorted lists | 可用于未排序列表 | Requires sorted list | 需要排序列表 |
| Worst-case comparisons | 最坏情况比较次数 | n | Approx. log₂(n) | 约 log₂(n) |
| Best-case comparisons | 最佳情况比较次数 | 1 | 1 |
| Complexity class | 复杂度类别 | O(n) linear time | 线性时间 | O(log n) logarithmic time | 对数时间 |
| Implementation | 实现难度 | Simple, easy to code | 简单，易于编码 | Slightly more complex, requires careful mid calculation | 稍微复杂，需要仔细计算中间值 |
| Typical use | 典型用途 | Small lists or unsorted data | 小列表或未排序数据 | Large sorted datasets | 大型排序数据集 |
If you have a very large dataset that is already sorted, binary search is almost always preferable. However, if the data is constantly changing or cannot be sorted efficiently, linear search might be the only viable option. The exam may ask you to justify your choice of algorithm in a given scenario.
如果你有一个非常大的且已排序的数据集，二分搜索几乎总是更优的选择。然而，如果数据不断变化或无法高效排序，线性搜索可能是唯一可行的选择。考试可能会要求你在给定场景中证明你选择算法的理由。
8. Algorithm Dry-Run and Tracing | 算法流程跟踪
WJEC past papers frequently ask students to dry-run a search algorithm on a small dataset. This means you must systematically work through the pseudocode, updating variable values and recording outputs. For binary search, a trace table is an excellent way to keep track of low, high, mid, and list[mid] at each iteration.
WJEC 历年真题经常要求学生在一个小数据集上对搜索算法进行流程跟踪。这意味着你必须系统地逐步执行伪代码，更新变量值并记录输出。对于二分搜索，跟踪表是记录每次迭代中 low、high、mid 和 list[mid] 值的绝佳方式。
When dry-running, be meticulous with integer division. For example, (0 + 7) DIV 2 = 3, and (3 + 4) DIV 2 = 3 because 7 DIV 2 = 3. The loop continues while low <= high. A common mistake is to forget that the loop terminates when low becomes greater than high, indicating the target is absent.
在进行流程跟踪时，要特别注意整除运算。例如，(0 + 7) DIV 2 = 3，而 (3 + 4) DIV 2 = 3，因为 7 DIV 2 = 3。只要 low <= high，循环就会继续。一个常见的错误是忘记了当 low 变成大于 high 时循环终止，这表明目标不存在。
Let us dry-run an unsuccessful binary search for target 10 in list [2, 5, 8, 12, 16]. Initially low=0, high=4. Mid=(0+4)DIV2=2, list[2]=8 < 10, so low=3. Now low=3, high=4, mid=(3+4)DIV2=3, list[3]=12 > 10, so high=2. Now low=3, high=2, loop condition low <= high is false; algorithm reports "Not found".
让我们对列表 [2, 5, 8, 12, 16] 中搜索目标 10 执行一次不成功的二分搜索。初始 low=0, high=4。mid=(0+4)DIV2=2，list[2]=8 < 10，所以 low=3。现在 low=3, high=4，mid=(3+4)DIV2=3，list[3]=12 > 10，所以 high=2。此时 low=3, high=2，循环条件 low <= high 为假；算法报告“Not found”。
9. Common Misconceptions and Exam Pitfalls | 常见误解与考试陷阱
One of the biggest mistakes students make is applying binary search to an unsorted list. The algorithm relies on the ordering to decide which half to discard. If the list is not sorted, binary search may return an incorrect result or miss the target entirely. The WJEC mark scheme expects you to explicitly state that the list must be sorted before using binary search.
学生最常犯的错误之一是将二分搜索应用于未排序的列表。该算法依赖于列表的顺序来决定舍弃哪一半。如果列表未排序，二分搜索可能返回错误结果或完全错过目标。WJEC 的评分标准要求你明确说明在使用二分搜索之前列表必须已排序。
Another pitfall is incorrectly updating the boundaries. After checking the middle element, you must set low = mid + 1 or high = mid - 1, not simply low = mid or high = mid. If you fail to exclude the middle element, you risk an infinite loop because the search interval might never shrink properly.
另一个陷阱是错误地更新边界。在检查中间元素后，你必须设置 low = mid + 1 或 high = mid - 1，而不是简单地 low = mid 或 high = mid。如果你没有排除中间元素，就有陷入无限循环的风险，因为搜索区间可能永远无法正确缩小。
Finally, some students confuse the worst-case number of comparisons. For linear search it is n; for binary search it is roughly the number of times you can halve n until you get to 1, which is log₂(n). You do not need to compute exact log values, but you should know that binary search is drastically more efficient for large n.
最后，一些学生会混淆最坏情况下的比较次数。线性搜索是 n；二分搜索大约是将 n 不断减半直到为 1 的次数，即 log₂(n)。你不需要计算精确的对数值，但你应该知道对于大的 n，二分搜索的效率要高得多。
10. Real-World Applications and Exam Context | 现实应用与考试背景
Search algorithms are not just theoretical concepts; they are used in countless applications. Whenever you look up a contact name in your phone's address book (which is sorted alphabetically), a binary search variant is likely used. Search engines, however, use far more complex algorithms, but understanding basic searching provides the foundation.
搜索算法不仅仅是理论概念；它们被用于无数应用程序中。每当你在手机通讯录中查找联系人姓名时（通讯录按字母顺序排序），很可能就使用了二分搜索的变体。然而，搜索引擎使用的算法要复杂得多，但理解基本搜索为其提供了基础。
In the WJEC examination, questions on searching often appear in Paper 2, which focuses on computational thinking and programming. You may be asked to write pseudocode, complete a trace table, explain the differences between algorithms, or suggest the most suitable algorithm for a scenario. Always read the question carefully to see if the list is sorted.
在 WJEC 考试中，关于搜索的题目通常出现在侧重计算思维和编程的试卷 2 中。你可能会被要求编写伪代码、完成跟踪表、解释算法之间的差异，或针对某个场景提出最合适的算法。一定要仔细阅读题目，确定列表是否已排序。
You might also encounter questions that combine searching with other concepts like arrays, file handling, or subprograms. For instance, you could be asked to write a program that reads data from a file into an array, sorts it, and then performs a binary search. Being comfortable with all these elements is essential.
你还可能遇到将搜索与数组、文件处理或子程序等其他概念结合起来的问题。例如，你可能会被要求编写一个程序，从文件中读取数据到数组中，对其进行排序，然后执行二分搜索。熟练掌握所有这些要素至关重要。
11. Summary of Key Learning Points | 核心学习要点总结
To excel in the search algorithms topic, ensure you can do the following:
- Describe the step-by-step process of linear and binary search.
- Write accurate pseudocode for both algorithms, including correct loop conditions and boundary updates.
- Explain the precondition for binary search (sorted data) and what happens if it is violated.
- Compare the efficiency of linear (O(n)) and binary (O(log n)) search in terms of maximum comparisons.
- Dry-run algorithms with given lists, producing correct trace tables.
- Identify suitable real-world scenarios for each algorithm.
要在搜索算法主题中取得优异成绩，请确保你能够做到以下几点：
- 描述线性和二分搜索的逐步过程。
- 为两种算法编写准确的伪代码，包括正确的循环条件和边界更新。
- 解释二分搜索的前提条件（数据已排序）以及违反条件时的后果。
- 从最大比较次数的角度比较线性搜索 (O(n)) 和二分搜索 (O(log n)) 的效率。
- 使用给定的列表对算法进行流程跟踪，生成正确的跟踪表。
- 为每种算法确定适合的现实场景。
Remember, practice is the key to mastering these concepts. Write out pseudocode from memory, test it with different datasets, and always double-check the sorting requirement when dealing with binary search. By solidifying these fundamentals, you will be well-prepared for any search-related question on your WJEC IGCSE Computer Science exam.
请记住，练习是掌握这些概念的关键。凭记忆写出伪代码，用不同的数据集进行测试，并在处理二分搜索时始终仔细确认排序要求。巩固这些基础知识后，你将对于 WJEC IGCSE 计算机科学考试中任何与搜索相关的问题都能做好充分准备。
Published by TutorHao | IGCSE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导