📚 IGCSE Computer Science: Search Algorithms Key Points | IGCSE 计算机：搜索算法考点精讲
Searching is one of the most fundamental operations in computer science, underpinning everything from simple database queries to web engines. In the IGCSE Computer Science syllabus, you are expected to understand, trace, implement, and compare two core search algorithms: linear search and binary search. This revision guide breaks down every key concept, common pitfalls, and exam-style applications so you can approach any search-related question with confidence.
搜索是计算机科学中最基本的操作之一，支撑着从简单数据库查询到网络引擎的各种应用。在 IGCSE 计算机科学大纲中，你需要理解、跟踪、实现并比较两种核心搜索算法：线性搜索和二分搜索。本复习指南详细剖析每个关键概念、常见陷阱和考试题型，助你从容应对搜索相关考题。
1. What is Searching? | 什么是搜索？
In computing, searching refers to the process of finding the position of a target value within a data structure, most commonly a one-dimensional array or list. The algorithm returns the index of the value if it exists, or an indication such as -1 when the value is not present. Searching enables data retrieval and is essential for tasks like looking up user records or checking for duplicate entries.
在计算领域，搜索是指在数据结构（最常见是一维数组或列表）中寻找目标值位置的过程。算法在该值存在时返回其索引，若不存在则返回诸如 -1 的指示。搜索实现了数据检索，对于查找用户记录或检查重复项等任务至关重要。
2. Linear Search: Step-by-Step | 线性搜索：逐步解析
Linear search, also called sequential search, works by examining each element of the array one by one from the first position to the last. If the current element matches the target, the search stops and returns that index. If the end of the array is reached without a match, the algorithm typically returns -1. Linear search does not require the data to be sorted – it works on any list, which makes it universally applicable.
线性搜索，又称顺序搜索，通过从第一个位置到最后一个位置逐一检查数组中的每个元素来工作。如果当前元素与目标匹配，搜索停止并返回该索引。如果到达数组末尾仍未匹配，算法通常返回 -1。线性搜索不要求数据已排序——它适用于任何列表，因此具有普遍适用性。
3. Linear Search: Pseudocode and Example | 线性搜索：伪代码与示例
Here is the standard pseudocode for linear search as expected in IGCSE exams. The algorithm receives an array and a target value. A variable ‘found’ can be used to store the result, initialised to -1. A FOR or WHILE loop iterates through indices 0 to length‑1. If a match occurs, the index is stored and the loop breaks.
以下是 IGCSE 考试所要求的线性搜索标准伪代码。算法接收一个数组和一个目标值。可用变量 ‘found’ 存储结果，初始化为 -1。一个 FOR 或 WHILE 循环遍历索引 0 至 length‑1。若出现匹配，存储索引并跳出循环。
FOR i ← 0 TO LENGTH(arr)-1
IF arr[i] = target THEN
found ← i
BREAK
ENDIF
ENDFOR
RETURN found
Example: Given the array [5, 3, 8, 2] and searching for 8, the algorithm checks index 0 (5 ≠ 8), index 1 (3 ≠ 8), index 2 (8 = 8) and returns 2. If searching for 7, all four elements would be checked and -1 returned.
示例：给定数组 [5, 3, 8, 2]，搜索 8，算法检查索引 0（5 ≠ 8）、索引 1（3 ≠ 8）、索引 2（8 = 8），返回 2。若搜索 7，则会检查全部四个元素后返回 -1。
4. Efficiency of Linear Search | 线性搜索的效率
Time complexity describes how an algorithm’s execution time grows with the input size n. Linear search has a best case of O(1) when the target is at the very first position. The worst case occurs when the target is at the last position or not present at all, requiring n comparisons: O(n). The average case also requires roughly n/2 comparisons, which is still classified as O(n). This linear growth means it becomes slow for very large datasets.
时间复杂度描述算法执行时间随输入规模 n 的增长情况。线性搜索的最佳情况是 O(1)，当目标恰好在第一个位置时。最坏情况发生在目标位于最后一个位置或完全不存在时，需进行 n 次比较：O(n)。平均情况大约需要 n/2 次比较，仍属于 O(n)。这种线性增长意味着对于非常大的数据集它会变慢。
5. Binary Search: Precondition and Process | 二分搜索：前提条件与过程
Binary search is a much faster algorithm, but it demands one strict precondition: the array must be sorted in ascending (or descending) order. It repeatedly divides the search interval in half. It maintains two boundaries, low and high. The middle index mid = (low + high) / 2 (or using integer division). If the middle element equals the target, the search stops. If the middle element is less than the target, the search continues on the right half (low = mid + 1). Otherwise, it continues on the left half (high = mid – 1). This halving drastically reduces the number of comparisons.
二分搜索是一种快得多的算法，但它要求一个严格的前提条件：数组必须按升序（或降序）排列。它反复将搜索区间对半分。维护两个边界 low 和 high。中间索引 mid = (low + high) / 2（或使用整数除法）。如果中间元素等于目标，搜索停止。若中间元素小于目标，则在右半部继续搜索（low = mid + 1）。否则，在左半部继续搜索（high = mid – 1）。这种对半分割极大地减少了比较次数。
6. Binary Search: Pseudocode and Example | 二分搜索：伪代码与示例
The IGCSE pseudocode for binary search is typically written with a WHILE loop that runs as long as low ≤ high. If low exceeds high, the target is not in the array, and the algorithm returns -1.
IGCSE 二分搜索伪代码通常使用 WHILE 循环，只要 low ≤ high 就继续。若 low 超过 high，则目标不在数组中，算法返回 -1。
low ← 0
high ← LENGTH(arr)-1
found ← -1
WHILE low ≤ high DO
mid ← (low + high) DIV 2
IF arr[mid] = target THEN
found ← mid
BREAK
ELSE IF arr[mid] < target THEN
low ← mid + 1
ELSE
high ← mid – 1
ENDIF
ENDWHILE
RETURN found
Example: Sorted array [2, 3, 5, 8, 11, 13], target = 8. Initial low=0, high=5, mid=(0+5) DIV 2=2: arr[2]=5 < 8, so low=3. Next mid=(3+5) DIV 2=4: arr[4]=11 > 8, so high=3. Next mid=(3+3) DIV 2=3: arr[3]=8, found at index 3. The search took only 3 comparisons instead of 4 with linear search on the same unsorted data.
示例：有序数组 [2, 3, 5, 8, 11, 13]，目标 = 8。初始 low=0, high=5, mid=(0+5) DIV 2=2：arr[2]=5 < 8，故 low=3。下一 mid=(3+5) DIV 2=4：arr[4]=11 > 8，故 high=3。下一 mid=(3+3) DIV 2=3：arr[3]=8，在索引 3 处找到。搜索仅用了 3 次比较，而同样的未排序数据用线性搜索本需 4 次。
7. Efficiency of Binary Search | 二分搜索的效率
Binary search exhibits logarithmic time complexity. Each comparison halves the search space, so the maximum number of comparisons needed is roughly log₂ n. The best case is O(1) when the middle element happens to be the target. The average and worst case are both O(log n). This makes binary search dramatically faster than linear search for large n – for n = 1 000 000, linear search may need 1 000 000 checks, but binary search requires at most 20.
二分搜索呈现对数时间复杂度。每次比较将搜索空间减半，因此最多需要的比较次数大约为 log₂ n。最佳情况是 O(1)，当中间元素恰好为目标时。平均和最坏情况都是 O(log n)。这使得对于大规模 n，二分搜索比线性搜索快非常多——当 n = 1 000 000 时，线性搜索可能需要 1 000 000 次检查，而二分搜索最多只需 20 次。
8. Comparison: Linear vs Binary Search | 对比：线性搜索与二分搜索
The following table summarises the key differences that frequently appear in IGCSE exam questions. Understanding these distinctions helps you decide which algorithm to use and explain trade-offs.
下表总结了 IGCSE 考试中常见的关键差异。理解这些区别有助于你决定使用哪种算法并解释权衡取舍。
| Feature | Linear Search | Binary Search |
| Data requirement | Works on unsorted data | Requires sorted data |
| Time complexity (worst) | O(n) | O(log n) |
| Time complexity (best) | O(1) | O(1) |
| Simplicity | Very easy to implement | More logic with boundaries |
| Works on linked lists | Yes | No (no direct random access) |
9. When to Use Each Algorithm | 如何选择搜索算法
Use linear search when the dataset is small, unsorted, or the data structure does not support direct indexing (e.g. linked list traversal). It is also simpler when searching is infrequent. Binary search should be chosen when the array is already sorted and the application requires frequent lookups on large sets. Note that sorting itself takes O(n log n), so if you only need to search once, linear search might be more efficient overall.
当数据集较小、无序，或数据结构不支持直接索引（如链表的遍历）时，使用线性搜索。若搜索不频繁，它也更简单。当选数组已排序，且应用需在大数据集上频繁查找时，应选择二分搜索。需要注意的是，排序本身需要 O(n log n) 时间，因此如果只需搜索一次，线性搜索总体上可能更高效。
10. Common Exam Pitfalls | 常见考试陷阱
A frequent mistake is applying binary search to an unsorted array; always check (or be told) that the list is sorted. Another pitfall is mishandling mid-calculation – forgetting to use integer division (DIV) can generate non-integer indices. Off-by-one errors also occur when updating low and high, such as setting low = mid instead of mid + 1, which can cause infinite loops. Finally, ensure a result variable is returned correctly; many marks are lost by returning ‘found’ after a loop without checking if it was updated.
一个常见错误是将二分搜索应用于未排序的数组；务必检查（或题目会明示）列表已排序。另一个陷阱是中值计算处理不当——忘记使用整数除法（DIV）会产生非整数索引。更新 low 和 high 时还会发生差一错误，如将 low 设为 mid 而非 mid + 1，这会导致无限循环。最后，确保结果变量被正确返回；许多考生因在循环后直接返回 ‘found’ 而未检查它是否被更新而丢分。
11. Exam-style Questions and Tips | 考试题型与技巧
IGCSE exam papers often ask you to trace algorithms in a trace table, showing each iteration’s values of i (or low, high, mid) and the decision. Practice filling these tables accurately. You may also be asked to write pseudocode for either search, so memorise the standard patterns. Comparison questions require you to justify your choice using time complexity and data preconditions. For full marks, always state whether the data must be sorted and mention real-world scenarios such as a phone book search (binary) or scanning a shopping list (linear).
IGCSE 试卷常要求你在跟踪表中追踪算法，显示每次迭代的 i（或 low, high, mid）值和判断。练习准确填写这些表格。你还可能被要求为任一搜索编写伪代码，因此要熟记标准模式。对比题需要你运用时间复杂度和数据前提条件来论证你的选择。为获满分，请务必说明数据是否需要排序，并提及实际场景，如电话簿搜索（二分）或扫描购物清单（线性）。
12. Summary | 总结
Search algorithms are a core component of the IGCSE syllabus. Linear search is simple, requires no sorting, and has O(n) worst-case performance. Binary search requires sorted data and achieves O(log n) efficiency through repeated halving. Master the pseudocode for both, understand the circumstances under which each is most suitable, and practise trace‑table exercises to avoid boundary errors. With these fundamentals secure, you will be well prepared for any search-related exam question.
搜索算法是 IGCSE 大纲的核心组成部分。线性搜索简单，无需排序，最坏性能为 O(n)。二分搜索要求数据有序，并通过反复对半分达到 O(log n) 效率。掌握两者的伪代码，理解各自最适用的环境，并练习跟踪表习题以避免边界错误。扎实掌握这些基础知识后，你就能从容应对任何搜索相关的考试题目。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导