📚 A-Level Computer Science: Search Algorithms – Key Concepts | A-Level 计算机：搜索算法考点精讲
Search algorithms lie at the heart of computer science. Whether you need to find an element in a list, a path in a maze, or the shortest route on a map, a solid grasp of search techniques is essential for A-Level success. This revision guide covers linear and binary search, tree and graph traversals, complexity analysis, and heuristic methods such as A*. Each concept is explained with clear comparisons and practical exam insights.
搜索算法是计算机科学的核心。无论是在列表中查找元素、在迷宫中寻找路径，还是在地图上规划最短路线，扎实掌握搜索技术对于 A-Level 考试至关重要。本复习指南涵盖线性搜索、二分查找、树与图的遍历、复杂度分析以及 A* 等启发式方法，每项内容都配有清晰的对比和实用的考试技巧。
1. Linear Search | 线性搜索
Linear search checks every element of an array or list sequentially until the target value is found or the end is reached. It works on unsorted data and requires no preprocessing.
线性搜索按顺序检查数组或列表中的每个元素，直到找到目标值或到达末尾。它适用于未排序的数据，无需任何预处理。
In the worst case, the algorithm examines all n elements, giving a time complexity of O(n). The best case occurs when the target is at the first position, yielding O(1).
在最坏情况下，算法需要检查全部 n 个元素，时间复杂度为 O(n)。最好情况是目标位于第一个位置，此时复杂度为 O(1)。
Linear search is simple to implement but inefficient for large datasets. It is often used when data is constantly changing or when searching is infrequent.
线性搜索实现简单，但对于大数据集效率较低。通常在数据频繁变化或搜索不频繁时使用。
2. Binary Search | 二分查找
Binary search repeatedly divides a sorted array in half, comparing the target with the middle element to eliminate one half each time. It only works on ordered data.
二分查找反复将已排序的数组对半分，将目标与中间元素进行比较，每次排除一半。它只适用于有序数据。
The algorithm maintains low and high pointers, calculates the mid index, and adjusts the search range based on the comparison. This halving process leads to a logarithmic time complexity of O(log n).
算法维护 low 和 high 指针，计算 mid 索引，并根据比较结果调整搜索范围。这种对半分的过程使得时间复杂度为对数级 O(log n)。
A recursive implementation is common, but exam questions may also ask for an iterative version. Always confirm that the array is sorted; otherwise, binary search will produce incorrect results.
递归实现很常见，但考题也可能要求迭代版本。务必确认数组已排序，否则二分查找将产生错误结果。
3. Search Efficiency and Complexity | 搜索效率与复杂度
Time complexity describes how the running time scales with input size. For linear search, average and worst-case complexities are O(n). Binary search averages O(log n), which grows much more slowly.
时间复杂度描述了运行时间随输入规模的变化。线性搜索的平均和最坏情况复杂度均为 O(n)。二分查找平均为 O(log n)，增长速度慢得多。
Space complexity is also relevant: linear search uses O(1) extra memory; binary search requires O(1) in its iterative form and O(log n) for the recursive call stack.
空间复杂度也很重要：线性搜索使用 O(1) 额外内存；迭代形式的二分查找使用 O(1)，递归调用栈则需 O(log n)。
Students should be able to compare the efficiency of search algorithms under different scenarios. Binary search is superior for static, sorted data, while linear search remains useful for small n or unsorted collections.
学生应能比较不同场景下搜索算法的效率。对于静态、有序的数据，二分查找更优；而对小规模 n 或无序集合，线性搜索仍有用武之地。
4. Binary Search Tree (BST) Search | 二叉搜索树查找
A binary search tree enforces the property that for any node, all values in the left subtree are smaller and those in the right subtree are larger. Searching follows a path from the root, moving left or right based on comparisons.
二叉搜索树的性质是：对于任一节点，左子树中的所有值都更小，右子树中的所有值都更大。查找从根开始，根据比较结果向左或向右移动。
The height of the tree determines the worst-case search cost. In a balanced BST, height is O(log n), so search is O(log n). In a degenerate (unbalanced) tree, height becomes O(n), degrading search to O(n).
树的高度决定了最坏情况下的查找代价。在平衡的 BST 中，高度为 O(log n)，因此搜索为 O(log n)。在退化（不平衡）的树中，高度变为 O(n)，搜索退化为 O(n)。
Exam questions often test insertion and search in a BST, as well as the importance of balancing. Self-balancing trees like AVL trees are mentioned but detailed balancing algorithms are usually beyond the scope.
考试中经常考查 BST 的插入与查找，以及平衡的重要性。AVL 树等自平衡树会被提及，但详细的平衡算法通常不考。
5. Graph Search Overview | 图搜索概述
Graphs model relationships with vertices and edges. Searching a graph means visiting nodes systematically to find a target or explore all reachable parts. Two fundamental strategies are depth-first search (DFS) and breadth-first search (BFS).
图用顶点和边表示关系。图的搜索意味着系统地访问节点以找到目标或探索所有可达部分。两种基本策略是深度优先搜索（DFS）和广度优先搜索（BFS）。
Graphs can be represented using adjacency matrices (O(V²) space) or adjacency lists (O(V+E) space), and the choice affects search efficiency. Both DFS and BFS work on unweighted graphs; weighted graphs often need more advanced algorithms.
图可以用邻接矩阵（O(V²) 空间）或邻接表（O(V+E) 空间）表示，选择会影响搜索效率。DFS 和 BFS 都适用于无权图；加权图通常需要更高级的算法。
6. Depth-First Search (DFS) | 深度优先搜索
DFS explores as far as possible along each branch before backtracking. It uses a stack, either explicitly or via recursion. A visited set prevents revisiting nodes and infinite loops in cyclic graphs.
DFS 在回溯之前沿着每条分支尽可能深入。它使用栈（显式或通过递归）。已访问集合可防止在环图中重复访问和无限循环。
The order of DFS can be pre-order, in-order, or post-order when applied to trees. For general graphs, the traversal order depends on the stack discipline. Time complexity is O(V+E) for adjacency lists.
应用于树时，DFS 的顺序可以是前序、中序或后序。对于一般图，遍历顺序取决于栈的处理方式。使用邻接表的时间复杂度为 O(V+E)。
DFS is useful for detecting cycles, topological sorting, and solving puzzles like mazes. It can be memory-efficient because it only stores a single path plus unexplored siblings.
DFS 可用于环检测、拓扑排序以及迷宫等谜题。它内存效率较高，因为只存储单条路径以及未探索的兄弟节点。
7. Breadth-First Search (BFS) | 广度优先搜索
BFS explores all neighbours at the present depth before moving to nodes at the next depth level. A queue is used to maintain the front of the exploration. Like DFS, a visited set is necessary.
BFS 在进入下一深度之前先探索当前深度的所有邻居。使用队列来维护探索前沿。与 DFS 一样，需要已访问集合。
BFS guarantees the shortest path in terms of the number of edges on unweighted graphs. Its time complexity is also O(V+E) with adjacency lists, but the memory requirement is typically larger than DFS because it stores all child pointers at the current level.
在无权图中，BFS 能保证找到边数最少的最短路径。使用邻接表的时间复杂度也为 O(V+E)，但内存需求通常大于 DFS，因为它需要存储当前层级的所有孩子节点。
Applications include web crawling, social network friend suggestions, and shortest-path problems on grid maps. In exams, you may be asked to trace BFS order or compare it with DFS.
应用包括网页爬取、社交网络好友推荐以及网格地图上的最短路径问题。考试中可能要求跟踪 BFS 顺序或与 DFS 进行比较。
8. Comparison of DFS and BFS | DFS 与 BFS 的对比
| Criteria | DFS | BFS |
|---|---|---|
| Data structure | Stack (LIFO) | Queue (FIFO) |
| Completeness | Complete in finite graphs if visited set is used | Complete in finite graphs |
| Optimal for unweighted shortest path | No | Yes |
| Memory usage | O(bm) with branching factor b and max depth m; often lower | O(bˡ) where l is the depth of the solution; can be high |
（表格注：DS 指数据结构，completeness 指在有解时能否找到，optimal 指路径边数最少。）
Choosing between DFS and BFS depends on the problem. Use BFS when the shortest path matters and the graph is not too wide; use DFS when the solution is deep or memory is constrained.
在 DFS 和 BFS 之间选择取决于问题。当最短路径重要且图不太宽时用 BFS；当解很深或内存受限时用 DFS。
9. Dijkstra's Algorithm and Shortest Path | Dijkstra 算法与最短路径
Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to repeatedly select the unvisited vertex with the smallest tentative distance.
Dijkstra 算法可在具有非负边权的加权图中，找到从源顶点到所有其他顶点的最短路径。它使用优先队列反复选取暂定距离最小的未访问顶点。
The algorithm relaxes edges: if distance[u] + weight(u,v) < distance[v], it updates distance[v]. With an array, complexity is O(V²); with a binary heap it becomes O((V+E) log V).
算法进行边的松弛：若 distance[u] + weight(u,v) < distance[v]，则更新 distance[v]。使用数组时复杂度为 O(V²)；使用二叉堆时为 O((V+E) log V)。
Dijkstra does not work with negative weights; the Bellman–Ford algorithm is used in that case. Typical A-Level questions require tracing the algorithm on a small graph and understanding termination.
Dijkstra 不适用于负权边，此时需用 Bellman–Ford 算法。典型的 A-Level 题目要求在一个小图上跟踪算法执行并理解终止条件。
10. A* Search Algorithm (Heuristic) | A* 搜索算法（启发式）
t expands nodes with the lowest f-value first, using a priority queue similar to Dijkstra.
A* 将到达节点的代价 (g) 和到目标的启发式估计值 (h) 结合为 f = g + h。它优先扩展 f 值最小的节点，使用的优先队列类似于 Dijkstra。
The heuristic must be admissible – it never overestimates the true cost to the goal. A consistent (monotonic) heuristic guarantees optimality without reopening nodes. Common heuristics include Manhattan distance and straight-line distance.
启发式函数必须是可接受的——不会高估到达目标的真实代价。一致的（单调的）启发式函数可确保最优性且无需重新打开节点。常见的启发函数包括曼哈顿距离和直线距离。
ates to Dijkstra’s algorithm. Exam questions may ask to identify a valid heuristic or compare A* with greedy best-first search.
A* 广泛用于游戏寻路和 GPS。当 h(n) = 0 时，A* 退化为 Dijkstra 算法。考题可能要求识别有效的启发式或比较 A* 与贪婪最佳优先搜索。
11. Applications and Exam Tips | 应用与考试技巧
Search algorithms appear in both theoretical and practical contexts. You might be asked to write pseudocode for linear or binary search, trace DFS/BFS on a given graph, or explain why Dijkstra cannot handle negative edges.
搜索算法会出现在理论和实践题中。你可能需要写出线性搜索或二分查找的伪代码，在给定图上跟踪 DFS/BFS，或解释 Dijkstra 为何不能处理负权边。
Common pitfalls include forgetting to check for an empty data structure, failing to mark nodes as visited in graph traversal, applying binary search on unsorted data, and confusing time complexities. Always consider edge cases and justify your choice of algorithm.
常见错误包括忘记检查空数据结构、在图遍历时未标记已访问节点、对未排序数据使用二分查找，以及混淆时间复杂度。务必考虑边界情况并论证算法选择的理由。
Revision should combine understanding with practice. Draw the search tree, simulate the queue/stack, and calculate complexity step by step. For A* and Dijkstra, practice updating distance tables until you can do it quickly and accurately.
复习时应将理解与练习结合。画出搜索树，模拟队列/栈，逐步计算复杂度。对于 A* 和 Dijkstra，练习更新距离表，直到能快速准确完成。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图