📚 A-Level WJEC Computer Science: Searching Algorithms | A-Level WJEC 计算机：搜索 考点精讲
Searching is a fundamental operation in computer science that involves finding a specific data item within a collection of data. In the WJEC A-Level specification, students must understand the principles, implementations, and efficiency of several core searching algorithms, including linear search, binary search, binary search tree operations, hash table lookups, and basic graph traversal methods. This guide covers each of these topics with step-by-step explanations, pseudocode conventions, and complexity analysis.
搜索是计算机科学中的基本操作，指在数据集合中查找特定数据项。根据 WJEC A-Level 大纲，学生需要理解线性搜索、二分搜索、二叉搜索树操作、哈希表查找以及基本图遍历方法的原理、实现和效率。本指南逐步讲解每个主题，包括伪代码约定和复杂度分析。
1. Introduction to Searching Algorithms | 搜索算法导论
Searching algorithms are designed to retrieve information stored within some data structure. The choice of algorithm depends on the organisation of data and the frequency of searches. We evaluate algorithms primarily by their time complexity, often expressed using Big O notation, and by their space requirements. WJEC candidates should be able to explain why a particular search method is suitable for a given scenario.
搜索算法旨在检索存储在数据结构中的信息。算法的选择取决于数据的组织方式和搜索频率。我们主要用时间复杂度（通常以大 O 记号表示）和空间需求来评估算法。WJEC 考生应能解释为何某种搜索方法适用于特定场景。
2. Linear Search – Iterative and Recursive | 线性搜索 – 迭代与递归
Linear search sequentially checks each element of a list until a match is found or the whole list has been searched. It does not require the data to be sorted. The worst-case and average-case time complexity is O(n). A simple iterative implementation uses a loop, while recursion can be used to mimic the same behaviour with an index parameter.
线性搜索逐个检查列表中的每个元素，直到找到匹配项或搜索完整个列表。它不要求数据有序。最坏和平均情况的时间复杂度为 O(n)。简单的迭代实现使用循环，而递归则通过索引参数模拟相同的行为。
The iterative pseudocode for linear search on an array A of size n, searching for value x:
在大小为 n 的数组 A 上搜索值 x 的迭代伪代码：
for i = 0 to n-1
if A[i] == x then return i
end for
return -1
The recursive version requires an extra parameter for the current index. Base cases: if index exceeds bounds, return -1; if element matches, return index. Recursion depth can reach n, so in practice iterative is preferred except for educational purposes.
递归版本需要额外的当前索引参数。基本情况：若索引越界则返回 -1；若元素匹配则返回索引。递归深度可达 n，因此除教学目的外，实际中优先使用迭代。
3. Binary Search Algorithm | 二分搜索算法
Binary search works on a sorted array by repeatedly dividing the search interval in half. It compares the target value to the middle element; if they are not equal, the half in which the target cannot lie is eliminated. This algorithm runs in O(log n) time, making it significantly faster than linear search for large datasets.
二分搜索适用于有序数组，通过反复将搜索区间减半来工作。它将目标值与中间元素比较；若不相等，则排除目标不可能存在的那一半。该算法的时间复杂度为 O(log n)，对于大数据集远快于线性搜索。
Binary search can be implemented iteratively using low and high pointers. Pseudocode:
二分搜索可使用 low 和 high 指针迭代实现。伪代码：
low = 0
high = n-1
while low ≤ high
mid = (low + high) div 2
if A[mid] == x then return mid
else if A[mid] < x then low = mid + 1
else high = mid - 1
end while
return -1
Recursive binary search splits the problem into a smaller sub-problem. It is essential to avoid integer overflow when computing mid; using low + (high – low) div 2 is safer in languages with fixed-width integers, though WJEC pseudocode generally ignores this detail.
递归二分搜索将问题拆分为更小的子问题。计算中间位置时需避免整数溢出，在定宽整数的语言中 low + (high – low) div 2 更安全，但 WJEC 伪代码通常忽略此细节。
4. Time Complexity Comparison: Linear vs Binary | 时间复杂度比较：线性与二分
The fundamental difference in complexity explains why sorting before searching can be beneficial. The table below summarises the performance characteristics. For a single search, linear search is O(n); for k searches on unsorted data, it becomes O(kn). If we sort first (O(n log n)) and then perform binary searches, total cost is O(n log n + k log n), which for large k is superior.
复杂度的根本差异解释了为何先排序再搜索可能更有利。下表总结了性能特征。对于单次搜索，线性搜索为 O(n)；若在未排序数据上执行 k 次搜索，则为 O(kn)。如果先排序（O(n log n)）再进行二分搜索，总成本为 O(n log n + k log n)，当 k 很大时更优。
| Algorithm | Best Case | Average Case | Worst Case | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) iterative O(log n) recursive |
Both algorithms have similar best cases (finding the item immediately), but the average and worst cases diverge dramatically as n grows.
两种算法的最佳情况相似（立即找到目标），但随着 n 增长，平均和最坏情况的差异急剧扩大。
5. Binary Search Tree (BST) Fundamentals | 二叉搜索树（BST）基础
A binary search tree is a rooted binary tree where each node contains a key, and for every node: all keys in its left subtree are less than the node's key, and all keys in its right subtree are greater. Searching in a BST follows a path from root to leaf, comparing the target with the current node and moving left or right accordingly.
二叉搜索树是一种有根二叉树，每个节点包含一个键，且对于每个节点：其左子树中的所有键都小于该节点的键，右子树中的所有键都大于该节点的键。在 BST 中搜索时，从根到叶沿路径比较目标与当前节点，并相应地左移或右移。
A well-balanced BST yields search times of O(log n), whereas a degenerate (linear) tree leads to O(n). Self-balancing trees such as AVL or red-black trees are not explicitly required by WJEC, but students should recognise how tree shape impacts performance.
平衡良好的 BST 搜索时间为 O(log n)，而退化（线性）树则是 O(n)。WJEC 不明确要求 AVL 或红黑树等自平衡树，但学生应认识到树的形状如何影响性能。
6. BST Search Operation – Algorithm and Pseudocode | BST 搜索操作 – 算法与伪代码
Given a BST root pointer and a target key, the search function recursively descends. If the tree is empty, the key is absent. Otherwise, compare the target with the current node's key: if equal, return the node; if less, search left subtree; if greater, search right subtree.
给定 BST 根指针和目标键，搜索函数递归下降。若树为空，则键不存在。否则，将目标与当前节点的键比较：若相等则返回该节点；若更小则搜索左子树；若更大则搜索右子树。
Pseudocode for recursive BST search:
递归 BST 搜索的伪代码：
function searchBST(node, key)
if node == null then return null
if key == node.key then return node
else if key < node.key then
return searchBST(node.left, key)
else
return searchBST(node.right, key)
end function
Iterative implementation avoids recursion and uses a while loop to traverse. This is more memory-efficient (O(1) space).
迭代实现避免递归，使用 while 循环遍历，内存效率更高（O(1) 空间）。
7. Hash Table Searching | 哈希表搜索
Hash tables store key-value pairs and use a hash function to compute an index from the key. Searching ideally takes O(1) time on average, making it extremely fast for exact-match queries. Collisions occur when two keys hash to the same index; strategies include separate chaining (linked list at each bucket) and open addressing (probing).
哈希表存储键值对，并使用哈希函数根据键计算索引。搜索平均理想情况下耗时 O(1)，对于精确匹配查询极快。当两个键哈希到同一索引时发生冲突；策略包括分离链接法（每个桶挂链表）和开放寻址法（探测）。
For a hash table with chaining, the search operation computes the hash, goes to the bucket, and performs a linear search within that bucket. The worst-case complexity is O(n) when all keys collide, but with a good hash function and load factor maintained, it is O(1) on average. WJEC expects students to understand the impact of load factor and collisions.
对于采用链地址法的哈希表，搜索操作计算哈希值，找到桶，并在桶内执行线性搜索。当所有键冲突时最坏情况时间复杂度为 O(n)，但使用良好的哈希函数并维持合适的装载因子，平均为 O(1)。WJEC 期望学生理解装载因子和冲突的影响。
8. Depth-First Search (DFS) on Graphs | 图的深度优先搜索
Graph traversal is a type of searching over vertices and edges. DFS explores as far as possible along each branch before backtracking. It can be implemented recursively or with a stack. DFS is useful for detecting cycles, topological sorting, and pathfinding in mazes.
图遍历是对顶点和边的搜索。DFS 尽可能沿着每条分支深入探索，然后再回溯。可以用递归或栈实现。DFS 可用于检测环、拓扑排序和迷宫寻路。
Pseudocode for DFS starting at vertex v, marking visited to avoid cycles:
从顶点 v 开始的 DFS 伪代码，标记已访问以避免环：
procedure DFS(v)
mark v as visited
for each neighbour u of v
if u is not visited then
DFS(u)
end for
end procedure
DFS time complexity is O(V + E) for an adjacency list, where V is the number of vertices and E the number of edges. The space complexity for the stack (recursion) can be O(V) in the worst case of a deep graph.
对于邻接表，DFS 的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。栈（递归）的空间复杂度在最深的图情况下可达 O(V)。
9. Breadth-First Search (BFS) on Graphs | 图的广度优先搜索
BFS explores all neighbours of a vertex before moving to the next level. It uses a queue to manage the order of exploration. BFS finds the shortest path in an unweighted graph and is used in peer-to-peer networks, social network analysis, and web crawling.
BFS 在进入下一层之前先探索顶点的所有邻居。它使用队列管理探索顺序。BFS 可在无权图中找到最短路径，并用于对等网络、社交网络分析和网络爬虫。
BFS algorithm pseudocode:
BFS 算法伪代码：
procedure BFS(start)
create a queue Q
mark start as visited and enqueue
while Q is not empty
v = dequeue(Q)
for each neighbour u of v
if u is not visited then
mark u as visited and enqueue(u)
end for
end while
end procedure
Like DFS, BFS runs in O(V + E) time with an adjacency list. The queue may hold up to O(V) vertices. BFS is particularly suitable for finding the shortest path in terms of number of edges.
与 DFS 类似，BFS 使用邻接表的时间为 O(V + E)。队列最多可容纳 O(V) 个顶点。BFS 特别适合按边数寻找最短路径。
10. Searching in Unsorted vs Sorted Data Structures | 未排序与有序数据结构中的搜索
The data structure's organisation dictates the applicable search strategy. Linear search is the only straightforward option for unsorted arrays or linked lists. For sorted arrays, binary search is optimal. For dynamic datasets that need frequent insertion and search, binary search trees or hash tables provide better trade-offs. WJEC questions often ask students to justify the choice of algorithm based on data size, volatility, and memory constraints.
数据结构的组织方式决定了可用的搜索策略。线性搜索是未排序数组或链表的唯一直接选择。对于有序数组，二分搜索是最优的。对于需要频繁插入和搜索的动态数据集，二叉搜索树或哈希表提供了更好的权衡。WJEC 试题经常要求学生根据数据规模、变更频率和内存限制来证明算法选择的合理性。
A summary of typical scenarios:
典型场景总结：
| Scenario | Recommended Search |
|---|---|
| Small unsorted list (n < 50) | Linear search |
| Large static sorted array | Binary search |
| Frequent insertions and deletions with search | Balanced BST or Hash table |
| Exact-match queries, no ordering needed | Hash table |
| Graph connectivity and traversal | DFS or BFS |
The ability to map a real-world problem to the appropriate data structure and searching algorithm is a key assessment objective.
将现实问题映射到适当的数据结构和搜索算法的能力是关键的评估目标。
11. Common Exam Pitfalls and Tips | 常见考试误区与提示
Many candidates lose marks by confusing iterative and recursive implementations, or by failing to handle edge cases such as empty lists, target not found, or mid calculation overflow. In BST search, forgetting to check for null pointers leads to runtime errors. In graph traversal, not tracking visited nodes causes infinite loops. Always dry-run your pseudocode with small examples, and annotate each line to show your understanding.
许多考生因混淆迭代和递归实现，或未能处理空列表、目标未找到、中间索引计算溢出等边界情况而失分。在 BST 搜索中，忘记检查空指针会导致运行时错误。在图遍历中，不跟踪已访问节点会造成无限循环。务必使用小样例手动执行伪代码，并为每一行注释以展示你的理解。
WJEC mark schemes reward clear, well-structured pseudocode, explicit comparison of complexities, and the ability to explain trade-offs in a real-world context. Practise writing both iterative and recursive versions, and be prepared to compare them in terms of memory usage and stack depth.
WJEC 评分标准看重清晰、结构良好的伪代码，明确的复杂度比较，以及在现实情境下解释权衡的能力。练习编写迭代和递归版本，并准备好比较它们在内存使用和栈深度方面的差异。
12. Summary and Future Learning | 总结与延伸学习
Mastering searching algorithms equips you with the tools to design efficient software solutions. From the simple linear search to the sophisticated graph traversals, each algorithm offers a different cost-benefit profile. As you progress, you will encounter more advanced structures like B-trees, tries, and Bloom filters that further optimise search operations. For your WJEC preparation, ensure you can write the core algorithms from memory, state their complexities, and apply them to novel problems.
掌握搜索算法为你提供了设计高效软件解决方案的工具。从简单的线性搜索到复杂的图遍历，每种算法都有不同的成本效益特性。随着学习的深入，你会遇到更高级的结构，如 B 树、字典树和布隆过滤器，它们进一步优化搜索操作。为准备 WJEC 考试，请确保你能默写核心算法、陈述它们的复杂度，并将其应用到新问题中。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图