Mastering Search Algorithms for IB WJEC Computer Science | IB WJEC 计算机：搜索考点精讲

📚 Mastering Search Algorithms for IB WJEC Computer Science | IB WJEC 计算机：搜索考点精讲

Searching is a fundamental operation in computer science, enabling efficient retrieval of data from collections. In the IB and WJEC specifications, understanding search algorithms—both linear and binary—is essential for algorithmic thinking, complexity analysis, and practical coding. This guide breaks down key concepts, pseudocode, efficiency, and exam-focused tips to help you master the topic.

搜索是计算机科学中的一项基本操作，它能够高效地从数据集合中检索信息。在 IB 和 WJEC 课程大纲中，理解搜索算法（包括线性搜索和二分搜索）对于算法思维、复杂度分析和实际编程都至关重要。本指南将详细拆解关键概念、伪代码、效率以及应试技巧，帮助你掌握这一考点。

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

Searching refers to the process of finding a target element within a collection of data. The collection can be an array, list, file, or database. The efficiency of a search depends on the algorithm used and the structure of the data (sorted vs unsorted). For IB and WJEC, you need to know both simple linear search and more sophisticated binary search.

搜索是指在数据集合中查找目标元素的过程。该集合可以是数组、列表、文件或数据库。搜索的效率取决于所使用的算法以及数据的结构（有序或无序）。对于 IB 和 WJEC 考试，你需要掌握简单的线性搜索和更复杂的二分搜索。

2. Linear Search – The Sequential Approach | 线性搜索——顺序查找法

Linear search (also called sequential search) iterates through each element of a collection one by one until the target is found or the end is reached. It works on both sorted and unsorted data, making it versatile but potentially slow for large datasets.

线性搜索（也称顺序搜索）逐个遍历集合中的每个元素，直到找到目标或到达末尾。它既适用于有序数据，也适用于无序数据，因此通用性强，但对于大数据集可能速度较慢。

Best-case time complexity: O(1) – target is the first element.
Worst-case time complexity: O(n) – target is the last element or not present.
Space complexity: O(1) – uses only a few variables.

最佳情况时间复杂度：O(1)——目标为第一个元素。
最坏情况时间复杂度：O(n)——目标为最后一个元素或不存在。
空间复杂度：O(1)——仅使用少量变量。

IB/WJEC pseudocode style:

i ← 0
while i < len(arr) AND arr[i] ≠ target
    i ← i + 1
endwhile
if i < len(arr)
    return i
else
    return -1
endif

Exam tip: Be ready to trace a linear search on a given array and state the number of comparisons made.

考试提示：准备好对给定数组进行线性搜索的跟踪，并说明所进行的比较次数。

3. Binary Search – Divide and Conquer | 二分搜索——分治法

Binary search works exclusively on sorted arrays. It repeatedly divides the search interval in half, comparing the target with the middle element. If the target equals the middle, search ends; if smaller, the left half is searched; if larger, the right half. This drastically reduces the number of comparisons.

二分搜索仅适用于有序数组。它反复将搜索区间一分为二，将目标与中间元素进行比较。如果目标等于中间元素，搜索结束；如果目标更小，则搜索左半部分；如果更大，则搜索右半部分。这大大减少了比较次数。

Time complexity: O(log n) in the worst case.
Space complexity: O(1) for iterative implementation, O(log n) for recursive due to call stack.

时间复杂度：最坏情况 O(log n)。
空间复杂度：迭代实现为 O(1)，递归实现由于调用栈而为 O(log n)。

Pseudocode (iterative):

low ← 0
high ← len(arr) – 1
while low ≤ high
    mid ← (low + high) / 2 // integer division
    if arr[mid] = target
        return mid
    elseif arr[mid] < target
        low ← mid + 1
    else
        high ← mid – 1
    endif
endwhile
return -1

Remember: The array must be sorted beforehand. WJEC often asks for a dry run with a specific data set.

注意：数组必须事先排序。WJEC 常常要求用具体数据集进行手工模拟执行。

4. Sorting as a Prerequisite | 排序作为前置条件

Binary search demands sorted data. Common sorting algorithms like bubble sort, insertion sort, or merge sort can be used, but that adds O(n log n) or O(n²) preprocessing time. If you need to search many times, the sorting cost is amortised. For a single search, linear search may be more efficient if data is unsorted.

二分搜索要求数据有序。可以使用冒泡排序、插入排序或归并排序等常见排序算法，但这会带来 O(n log n) 或 O(n²) 的预处理时间。如果需要多次搜索，排序成本可以被分摊。对于单次搜索，如果数据无序，线性搜索可能更高效。

IB/WJEC exam questions may ask: “Explain why the data must be sorted before using binary search.” The answer lies in the algorithm’s logic—it relies on comparisons that direct the search left or right based on ordering.

IB/WJEC 考题可能会问：“解释为什么在使用二分搜索之前必须对数据进行排序。” 答案在于算法的逻辑——它依赖于根据大小顺序将搜索引向左或右的比较操作。

5. Recursive vs Iterative Implementations | 递归与迭代实现对比

Both linear and binary search can be implemented recursively, but linear search is rarely written recursively because it offers no advantage. Binary search, however, naturally fits recursion due to its divide-and-conquer nature.

线性搜索和二分搜索都可以递归实现，但线性搜索很少写成递归形式，因为没有什么优势。然而，二分搜索由于其分治特性，非常适合递归。

Recursive binary search (pseudocode):

function binarySearch(arr, target, low, high)
    if low > high return -1
    mid ← (low + high) / 2
    if arr[mid] = target return mid
    elseif arr[mid] < target
        return binarySearch(arr, target, mid+1, high)
    else
        return binarySearch(arr, target, low, mid-1)
    endif
endfunction

Iterative is often preferred in constrained memory environments to avoid stack overflow, but recursive code can be more elegant. IB tends to accept both, but you must identify the correct base case.

在内存受限的环境中，通常优先选择迭代方式以避免栈溢出，但递归代码可以更简洁。IB 通常两者都接受，但你必须正确识别基线条件。

6. Complexity Analysis and Big O Notation | 复杂度分析与大 O 表示法

For IB and WJEC Computer Science, you are expected to analyse algorithm efficiency in terms of time and space. Use Big O notation to express worst-case performance:

对于 IB 和 WJEC 计算机科学，你需要从时间和空间角度分析算法效率。使用大 O 表示法来表达最坏情况性能：

Algorithm	Best Time	Avg Time	Worst Time	Space
Linear Search	O(1)	O(n)	O(n)	O(1)
Binary Search	O(1)	O(log n)	O(log n)	O(1) iterative

Explain why binary search is O(log n): The search space halves with each step, so the maximum number of steps is log₂(n) + 1.

解释为什么二分搜索是 O(log n)：搜索空间每步减半，因此最大步骤数为 log₂(n) + 1。

In an exam, you might be asked to calculate the maximum comparisons for an array of size 1000: linear search = 1000; binary search ≈ 10 (since 2¹⁰ = 1024).

在考试中，你可能会被要求计算对于大小为 1000 的数组的最大比较次数：线性搜索 = 1000；二分搜索 ≈ 10（因为 2¹⁰ = 1024）。

7. Practical Considerations and Edge Cases | 实际考量与边界情况

Empty collection: Both algorithms should handle an empty array gracefully (return -1 immediately). In binary search, set low > high to stop.

空集合：两种算法都应妥善处理空数组（立即返回 -1）。在二分搜索中，通过 low > high 来终止。

Duplicate values: Neither algorithm guarantees which index is returned if the target appears multiple times. To find the first or last occurrence, modifications are needed (common in WJEC advanced tasks).

重复值：如果目标出现多次，两种算法都不保证返回哪个索引。要找到第一次或最后一次出现的位置，需要进行修改（在 WJEC 高级任务中常见）。

Data types: Searching works on any comparable data type (integers, strings, dates) as long as consistent ordering is defined.

数据类型：只要能定义一致的顺序，搜索可以作用于任何可比较的数据类型（整数、字符串、日期等）。

8. Common Exam Questions and How to Approach Them | 常见考题及应对策略

Typical IB/WJEC questions include:

Tracing an algorithm with given input.
Writing pseudocode for a search algorithm.
Comparing linear and binary search for a scenario.
Identifying the number of iterations/comparisons.
Modifying an algorithm to handle duplicates or return a count.

典型 IB/WJEC 题目包括：

用给定输入跟踪算法。
为搜索算法编写伪代码。
针对特定情景比较线性搜索和二分搜索。
识别迭代/比较的次数。
修改算法以处理重复项或返回计数。

Tracing tips: Use a table with variables (low, high, mid, arr[mid]) and update values step by step. Always check boundary conditions—often marks are lost when the loop terminates incorrectly.

跟踪技巧：使用包含变量（low、high、mid、arr[mid]）的表格，逐步更新数值。务必检查边界条件——常常因为循环终止错误而失分。

9. Extension: Searching Beyond Arrays | 扩展：数组之外的搜索

While the core syllabus focuses on arrays, searching extends to other data structures:

Binary search trees (BST): search is O(log n) on average.
Hash tables: constant-time O(1) average search (key lookup).
Linear search on linked lists due to lack of random access.

尽管核心大纲侧重于数组，但搜索还扩展到其他数据结构：

二叉搜索树 (BST)：平均搜索时间为 O(log n)。
哈希表：常数时间 O(1) 平均搜索（键查找）。
链表因其缺乏随机访问而使用线性搜索。

WJEC sometimes asks about searching a file or database, but the principles remain: sequential vs indexed access.

WJEC 有时会问及搜索文件或数据库，但其原理保持不变：顺序访问与索引访问。

10. Key Terminology Summary | 关键术语总结

Make sure you can define: search key (the value being searched for), comparison (operation checking equality or order), deterministic algorithm (same steps for same input), and efficiency (measured by time/space complexity).

确保你能够定义：搜索键（所要查找的值）、比较（检查相等性或顺序的操作）、确定性算法（相同输入对应相同步骤）以及效率（以时间/空间复杂度衡量）。

Memorise the typical log₂ approximations: 128 → 7, 1024 → 10, 1,000,000 → 20. These help in quick estimation questions.

记住典型的 log₂ 近似值：128 → 7，1024 → 10，1,000,000 → 20。这有助于快速估算问题。

11. Coding Pitfalls to Avoid | 需要避免的编程陷阱

Even when writing pseudocode, avoid:

Infinite loops: ensure low and high are updated to narrow the interval.
Off-by-one errors: mid calculation (integer division) and boundary updates.
Using ‘=’ vs ‘←’ incorrectly in pseudocode (IB likes ← for assignment).
Forgetting to return a value when the target is not found.

即使在写伪代码时，也要避免：

无限循环：确保更新 low 和 high 以缩小范围。
边界偏差：mid 的计算（整数除法）及边界更新。
在伪代码中错误使用 ‘=’ 与 ‘←’（IB 偏好用 ← 进行赋值）。
当目标未找到时忘记返回值。

12. Bringing It All Together – Exam Strategy | 总结——考试策略

Search algorithms are a core topic where you can easily get full marks if you practice tracing and writing clean pseudocode. Always justify your choice between linear and binary search based on whether the data is sorted, the size of the dataset, and how many searches are needed. Use correct terminology and show your workings for complexity calculations.

搜索算法是一个核心主题，只要练习跟踪和编写清晰的伪代码，就能轻松拿到满分。始终根据数据是否有序、数据集大小以及所需搜索的次数来论证你在线性搜索和二分搜索之间的选择。使用正确的术语，并展示复杂度计算的过程。

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

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

Mastering Search Algorithms for IB WJEC Computer Science | IB WJEC 计算机：搜索 考点精讲