📚 Search Algorithms for CIE A-Level Computer Science | CIE A-Level 计算机搜索算法考点精讲
Searching is the process of finding a specific piece of data from a collection. For CIE A-Level Computer Science, understanding different search algorithms and their efficiency is essential. This article covers linear search, binary search, binary search tree search, hashing, collision resolution, time complexities, and exam-focused tips.
搜索是从数据集合中查找特定数据项的过程。对于CIE A-Level计算机科学，理解不同的搜索算法及其效率至关重要。本文将涵盖线性搜索、二分搜索、二叉搜索树搜索、哈希、碰撞解决、时间复杂度以及考试技巧。
1. Introduction to Searching | 搜索简介
Searching underpins many operations in computing, from database queries to finding an element in an array. The choice of search algorithm depends on whether the data structure is ordered, the size of the dataset, and how frequently the search is performed. CIE exam questions often ask students to describe, compare, and apply these algorithms.
搜索是许多计算操作的基础，从数据库查询到在数组中查找元素。搜索算法的选择取决于数据结构是否有序、数据集的大小以及搜索的执行频率。CIE考题经常要求学生描述、比较和应用这些算法。
2. Linear Search | 线性搜索
Linear search (also called sequential search) checks each element of a list in turn until the target is found or the end is reached. It does not require the data to be sorted. The worst-case time complexity is O(n), where n is the number of elements. Although simple to implement, it becomes inefficient for large datasets.
线性搜索（又称顺序搜索）依次检查列表中的每个元素，直到找到目标或到达列表末尾。它不需要对数据进行排序。最坏情况时间复杂度为 O(n)，其中 n 是元素个数。虽然实现简单，但对于大型数据集效率低下。
In the best case, the target is at the first position, giving O(1). In the average case, about half the items are examined, still O(n). Linear search can be used on arrays, linked lists, and files.
在最好情况下，目标在第一个位置，复杂度为 O(1)。平均情况下，大约要检查一半的元素，仍为 O(n)。线性搜索可用于数组、链表和文件。
3. Binary Search | 二分搜索
Binary search works only on a sorted array. It repeatedly divides the search interval in half. The target is compared with the middle element; if it matches, the search ends. If the target is smaller, the search continues in the left half, otherwise in the right half. This reduces the problem size exponentially, giving a time complexity of O(log n).
二分搜索仅适用于已排序的数组。它反复将搜索区间减半。将目标与中间元素比较；如果匹配，搜索结束。如果目标较小，则在左半部分继续搜索，否则在右半部分。这使问题规模指数级减小，时间复杂度为 O(log n)。
Binary search can be implemented iteratively or recursively. The iterative version is often preferred due to lower memory overhead. It is far more efficient than linear search for large, sorted data. However, maintaining sorted order adds an overhead when inserting or deleting elements.
二分搜索可以迭代或递归实现。迭代版本因内存开销较低而更常被采用。对于大型有序数据，它比线性搜索高效得多。但是，在插入或删除元素时维持有序排列会增加额外开销。
For example, searching for 42 in a sorted array of 1000 elements takes at most 10 comparisons (since 2¹⁰ = 1024). Compare that with up to 1000 comparisons for linear search.
例如，在一个1000个元素的有序数组中搜索42最多需要10次比较（因为2¹⁰ = 1024）。对比线性搜索最多需要1000次比较。
4. Searching in a Binary Search Tree | 二叉搜索树中的搜索
A Binary Search Tree (BST) is a data structure where each node has at most two children, and for every node, all keys in the left subtree are smaller, and all keys in the right subtree are larger. Searching in a BST follows this property: start at the root, compare the target with the current node; if equal, found; if smaller, go left; if larger, go right. This continues until the node is found or a leaf is reached (null).
二叉搜索树是一种数据结构，每个节点最多有两个子节点，并且对于任意节点，左子树的所有键值均小于该节点，右子树的所有键值均大于该节点。在BST中搜索遵循这一性质：从根节点开始，将目标值与当前节点比较；若相等，则找到；若目标更小，则向左；若更大，则向右。持续此过程，直到找到节点或到达空指针。
The average-case time complexity for a balanced BST is O(log n), but in the worst case (e.g., degenerate tree), it can be O(n) if the tree becomes a linked list. Self-balancing trees like AVL maintain O(log n) search time.
平衡二叉搜索树的平均时间复杂度为 O(log n)，但最坏情况下（如退化成链表）可能为 O(n)。像AVL这样的自平衡树可以保持 O(log n) 的搜索时间。
5. Hash Tables and Hashing | 哈希表与哈希
A hash table uses a hash function to map keys to an index in an array, allowing near-constant-time O(1) average search. The hash function h(key) should distribute keys uniformly to minimise collisions. Common hash functions include modulo division (e.g., key mod table_size). Searching involves computing the hash of the target key, going directly to that slot, and checking if the key is present.
哈希表使用哈希函数将键映射到数组中的索引，从而实现接近常数时间的平均搜索 O(1)。哈希函数 h(key) 应均匀分布键以减少碰撞。常见的哈希函数包括取模运算（如 key mod 表大小）。搜索步骤是计算目标键的哈希值，直接访问该槽位，然后检查键是否存在。
If a collision occurs (two keys hash to the same index), extra steps are needed to locate the correct entry. That is where collision resolution methods come in.
如果发生碰撞（两个键映射到同一索引），则需要额外步骤来定位正确的条目。这就引入了碰撞解决方法。
6. Collision Resolution: Linear Probing and Chaining | 碰撞解决：线性探测与链地址法
Linear probing is an open addressing method: when a collision occurs at index i, the algorithm checks i+1, i+2, … (wrapping around) until an empty slot is found. During search, the same probing sequence is followed until the key is found or an empty slot is encountered, indicating the key is absent. Linear probing can lead to clustering, which degrades performance.
线性探测是一种开放地址法：当在索引 i 发生碰撞时，算法检查 i+1，i+2，……（循环）直至找到空槽。搜索时遵循相同的探测序列，直到找到键或遇到空槽，后者表示键不存在。线性探测可能导致聚集，降低性能。
Chaining uses a linked list at each array slot to store all keys that hash to that index. Searching involves hashing to the slot and then traversing the linked list. Chaining handles collisions gracefully and works well when the load factor is high. It is simpler to implement but uses extra memory for pointers.
链地址法在每个数组槽位使用一个链表来存储所有哈希到该索引的键。搜索步骤是先哈希到该槽位，然后遍历链表。链地址法能优雅地处理碰撞，在负载因子较高时也能良好工作。它实现更简单，但需要额外内存存储指针。
7. Time Complexities Comparison | 时间复杂度比较
The table below summarises the time complexities of the main search algorithms in Big O notation. This is a common exam point; students must be able to recall and compare these values.
下表总结了大O表示法下主要搜索算法的时间复杂度。这是常见的考点；学生必须能记住并比较这些值。
| Algorithm | Best Case | Average Case | Worst Case | Sorted data required? |
|---|---|---|---|---|
| Linear Search | 更多咨询请联系16621398022（同微信）
CommentsMore posts |
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导