📚 IGCSE Edexcel Computer Science: Searching Key Points | IGCSE Edexcel 计算机：搜索 考点精讲
Searching is a fundamental operation in computer science, where we locate a specific item (the target) within a collection of data. Efficient searching is essential for many applications, from finding a contact in a phone book to querying a database. In IGCSE Edexcel Computer Science, you need to understand two core searching algorithms: linear search and binary search, including how they work, when to use them, and their performance characteristics.
搜索是计算机科学中的一项基本操作，即在数据集合中定位特定项（目标）。高效搜索对于许多应用程序至关重要，从在电话簿中查找联系人到查询数据库。在 IGCSE Edexcel 计算机科学课程中，你需要理解两种核心搜索算法：线性搜索和二分搜索，包括它们的工作原理、使用时机以及性能特征。
1. Introduction to Searching Algorithms | 搜索算法简介
Searching algorithms are step-by-step procedures designed to locate a target value within a data structure, usually an array or list. The goal is to return the index (position) where the target is found, or a special value (like -1) if it is absent. Different algorithms trade off speed against the requirement that data be sorted.
搜索算法是逐步设计的程序，用于在数据结构（通常是数组或列表）中定位目标值。目标是返回找到目标的索引（位置），如果不存在则返回一个特殊值（如 -1）。不同算法在速度和数据排序要求之间做出权衡。
2. Why Searching is Important | 搜索为何重要
Searching is ubiquitous in computing. Whether you're looking up a username in a password file, filtering products by price on an e-commerce site, or checking for duplicates, a search operation lies at the heart of the process. Understanding the underlying algorithms helps you write efficient code and appreciate the impact of data organisation on performance.
搜索在计算中无处不在。无论你是在密码文件中查找用户名、在电子商务网站上按价格筛选产品，还是检查重复项，搜索操作都是过程的核心。理解底层算法有助于你编写高效的代码，并认识到数据组织对性能的影响。
3. Linear Search Explained | 线性搜索详解
Linear search, also known as sequential search, is the simplest method. It checks each element of the list in turn, from the first to the last, until a match is found or the end is reached. Because it does not rely on any ordering, it works on any list—sorted, unsorted, or even lists containing duplicate values. However, for large datasets it can be slow, as it may have to examine every single element.
线性搜索，也称顺序搜索，是最简单的方法。它依次检查列表中的每个元素，从第一个到最后一个，直到找到匹配或到达末尾。由于它不依赖任何排序，因此适用于任何列表——排序的、未排序的，甚至包含重复值的列表。然而，对于大数据集，它可能很慢，因为它可能需要检查每一个元素。
4. Linear Search: Step-by-Step Example | 线性搜索：分步示例
Suppose we have a list of numbers: [15, 8, 22, 6, 19] and we want to find the target 22. The algorithm starts at index 0 (value 15): not a match, move to index 1 (8): not a match, index 2 (22): match found! So it returns index 2. If the target were 10, it would check all five elements and then return -1 (not found).
假设我们有一个数字列表：[15, 8, 22, 6, 19]，我们要查找目标 22。算法从索引 0（值 15）开始：不匹配，移到索引 1（8）：不匹配，索引 2（22）：找到匹配！因此返回索引 2。如果目标是 10，它会检查所有五个元素，然后返回 -1（未找到）。
Here is a trace table for this example:
此示例的跟踪表：
- Index 0: 15 ≠ 22, continue. 索引 0：15 ≠ 22，继续。
- Index 1: 8 ≠ 22, continue. 索引 1：8 ≠ 22，继续。
- Index 2: 22 = 22, found at position 2. 索引 2：22 = 22，在位置 2 找到。
5. Binary Search Explained | 二分搜索详解
Binary search is a much faster algorithm, but it demands that the list be sorted in ascending (or descending) order. It repeatedly divides the search interval in half: compare the target with the middle element, then discard the half that cannot contain the target. This 'divide and conquer' approach drastically reduces the number of comparisons, making it feasible for very large sorted datasets.
二分搜索是一种快得多的算法，但它要求列表按升序（或降序）排序。它反复将搜索区间分成两半：将目标与中间元素比较，然后丢弃不可能包含目标的那一半。这种“分而治之”的方法大大减少了比较次数，使其适合非常大的有序数据集。
6. Binary Search: Pre-requisites and Steps | 二分搜索：前提条件与步骤
Pre-requisite: data must be sorted. The algorithm uses two pointers, low and high, that define the current search interval.
前提条件：数据必须已排序。该算法使用两个指针 low 和 high 来定义当前搜索区间。
The basic steps are:
基本步骤如下：
- Set low = 0, high = length of list - 1. 设置 low = 0，high = 列表长度 - 1。
- While low ≤ high: 当 low ≤ high 时：
- Calculate mid = (low + high) DIV 2 (integer division). 计算 mid = (low + high) 整除 2（整数除法）。
- If list[mid] equals target, return mid. 若 list[mid] 等于目标，返回 mid。
- If list[mid] < target, set low = mid + 1 (discard left half). 若 list[mid] < 目标，设 low = mid + 1（丢弃左半部分）。
- Else (list[mid] > target), set high = mid - 1 (discard right half). 否则（list[mid] > 目标），设 high = mid - 1（丢弃右半部分）。
- If the loop ends without returning, return -1 (not found). 若循环结束未返回，返回 -1（未找到）。
7. Binary Search: Step-by-Step Example | 二分搜索：分步示例
Consider the sorted list [3, 9, 12, 19, 25, 30, 42] and target 25.
考虑排序列表 [3, 9, 12, 19, 25, 30, 42] 和目标 25。
Iteration 1: low=0, high=6, mid=(0+6)//2=3 → list[3]=19. 19 < 25, so low becomes 4.
第一次迭代：low=0，high=6，mid=(0+6)//2=3 → list[3]=19。19 < 25，因此 low 变为 4。
Iteration 2: low=4, high=6, mid=(4+6)//2=5 → list[5]=30. 30 > 25, so high becomes 4.
第二次迭代：low=4，high=6，mid=(4+6)//2=5 → list[5]=30。30 > 25，因此 high 变为 4。
Iteration 3: low=4, high=4, mid=(4+4)//2=4 → list[4]=25. Match found! Return index 4.
第三次迭代：low=4，high=4，mid=(4+4)//2=4 → list[4]=25。找到匹配！返回索引 4。
If target were 10, the algorithm would eventually have low > high and return -1.
如果目标是 10，算法最终会出现 low > high 并返回 -1。
8. Comparing Linear and Binary Search | 比较线性搜索与二分搜索
Both algorithms have their strengths, and the choice depends on the data and the context.
两种算法各有优势，选择取决于数据和上下文。
- Linear search works on any list; binary search requires a sorted list. 线性搜索适用于任何列表；二分搜索需要排序列表。
- Linear search checks up to n elements in the worst case; binary search checks approximately log₂ n. 线性搜索在最坏情况下最多检查 n 个元素；二分搜索大约检查 log₂ n 个元素。
- For small n (e.g., n < 20), linear search's simplicity often makes it just as fast. 对于较小的 n（例如 n < 20），线性搜索的简单性通常使其速度相当。
- Binary search is far more efficient on large datasets but cannot be applied if the data changes frequently (cost of sorting). 二分搜索在大数据集上效率高得多，但如果数据频繁变动（排序成本高），则无法应用。
- Linear search is easier to code; binary search requires careful handling of indices to avoid infinite loops. 线性搜索更易编码；二分搜索需要小心处理索引以避免无限循环。
9. Pseudocode for Linear Search | 线性搜索伪代码
Below is a typical pseudocode representation. Exam questions may ask you to interpret or complete such pseudocode.
下面是典型的伪代码表示。考题可能要求你解释或补全这类伪代码。
Set i to 0.
将 i 设为 0。
WHILE i < LEN(list) AND list[i] ≠ target
当 i < 列表长度 且 list[i] ≠ 目标 时
i ← i + 1
将 i 增加 1
ENDWHILE
结束循环
IF i < LEN(list) THEN
如果 i < 列表长度 则
RETURN i
返回 i
ELSE
否则
RETURN -1
返回 -1
ENDIF
结束如果
rget is found, list[i] = target, so the second condition becomes false and the loop stops.
注意循环条件使用了 AND；两部分都必须为真才能继续。如果找到目标，list[i] = target，第二个条件变为假，循环停止。
10. Pseudocode for Binary Search | 二分搜索伪代码
The binary search pseudocode must manage the low and high pointers carefully.
二分搜索伪代码必须小心管理 low 和 high 指针。
low ← 0
low 设为 0
high ← LEN(list) - 1
high 设为 列表长度 - 1
WHILE low ≤ high
当 low ≤ high 时
mid ← (low + high) DIV 2
mid 设为 (low + high) 整除 2
IF list[mid] = target THEN
如果 list[mid] = 目标 则
RETURN mid
返回 mid
ELSEIF list[mid] < target THEN
否则如果 list[mid] < 目标 则
low ← mid + 1
low 设为 mid + 1
ELSE
否则
high ← mid - 1
high 设为 mid - 1
ENDIF
结束如果
ENDWHILE
结束循环
RETURN -1
返回 -1
Make sure you use integer division (DIV) so that mid is a valid index. Many errors in exams come from forgetting to update low and high correctly, leading to infinite loops.
确保使用整数除法 (DIV)，使 mid 成为有效索引。考试中的很多错误源于忘记正确更新 low 和 high，导致无限循环。
11. Exam Tips and Common Mistakes | 考试技巧与常见错误
In exams, you may be asked to trace the algorithm step by step using a given list. Always show the values of low, high and mid at each iteration. A common mistake is assuming binary search works on an unsorted list—if it's not sorted, you must either sort it first or use linear search. Also, watch out for off-by-one errors when setting initial high or when updating boundaries. Practice with both odd and even-length lists.
考试中，你可能会被要求使用给定列表逐步跟踪算法。每次迭代都要显示 low、high 和 mid 的值。一个常见错误是假设二分搜索适用于未排序列表——如果列表未排序，你必须先排序或使用线性搜索。此外，注意设置初始 high 或更新边界时的差一错误。使用奇数和偶数长度的列表进行练习。
12. Conclusion | 总结
Mastering linear and binary search algorithms will not only help you ace your IGCSE exam but also build a strong foundation for more advanced topics like data structures, algorithm efficiency, and the concept of divide and conquer. Practice tracing both algorithms with different datasets, and you'll be well-prepared for any question that comes your way.
掌握线性搜索和二分搜索算法不仅能帮助你在 IGCSE 考试中取得高分，还能为数据结构和算法效率、分治概念等更高级主题打下坚实基础。用不同的数据集练习跟踪这两种算法，你将能从容应对任何考题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图