📚 Search Algorithms in IB AQA Computer Science | IB AQA 计算机科学中的搜索算法考点精讲
In the IB AQA Computer Science syllabus, search algorithms form a fundamental component of algorithmic thinking and problem-solving. Understanding how data can be efficiently located within different data structures is essential for both your examinations and practical programming tasks. This article will guide you through the core concepts of searching, from simple linear approaches to more efficient binary methods, and explore how these techniques apply to arrays, lists, and tree structures.
在IB AQA计算机科学课程大纲中，搜索算法是算法思维和问题解决的基本组成部分。理解如何在不同数据结构中高效地定位数据，对于考试和实际编程任务都至关重要。本文将从简单的线性方法到更高效的二分法，带你梳理搜索的核心概念，并探讨这些技术如何应用于数组、链表和树结构。
1. What is Searching? | 什么是搜索？
Searching is the algorithmic process of finding a particular item, often referred to as the target or key, within a collection of data. The goal can be simply to determine whether the item exists, or to retrieve its position for further processing. The efficiency of a search depends heavily on the underlying data structure and whether the data is sorted.
搜索是在数据集合中查找特定项（通常称为目标或关键值）的算法过程。其目的可能只是判断该项是否存在，或获取其位置以便进一步处理。搜索的效率在很大程度上取决于底层数据结构以及数据是否已排序。
A search problem is formally defined by an input sequence of elements and a target value; the output is either the index where the target is found or a sentinel value indicating its absence. In AQA examinations, you are expected to describe, trace, and implement standard search algorithms, as well as compare their performance in terms of time complexity.
搜索问题在形式上由输入元素序列和目标值定义；输出要么是找到目标的索引，要么是一个表示其缺失的标记值。在AQA考试中，你应当能够描述、追踪和实现标准搜索算法，并能从时间复杂度方面比较它们的性能。
2. Linear Search: The Sequential Approach | 线性搜索：顺序查找方法
Linear search, also called sequential search, is the most straightforward searching technique. It begins at the first element and checks each subsequent element in turn until either the target is found or the end of the collection is reached. Because it does not assume any ordering of the data, it works on both unsorted and sorted arrays and lists.
线性搜索，也称顺序搜索，是最直接的查找技术。它从第一个元素开始，依次检查每个后续元素，直到找到目标或到达集合末尾。由于不假设数据有任何顺序，它可以用于未排序和已排序的数组与链表。
The linear search algorithm can be described in pseudocode as: for i = 0 to length-1, if arr[i] == target return i; return -1. In Python-like syntax, a while loop is often used. The worst-case scenario requires checking every element, giving it a time complexity of O(n) where n is the number of elements. This makes it inefficient for large datasets, yet sufficient for small ones or when a single search is needed on unsorted data.
线性搜索算法可用伪代码描述为：for i = 0 to length-1, if arr[i] == target return i; return -1。在类似Python的语法中，常使用while循环。最坏情况需要检查每个元素，时间复杂度为O(n)，其中n是元素个数。这使得它对大型数据集效率低下，但对于小型数据集或未排序数据的单次搜索来说已经足够。
In AQA exam questions, you may be asked to trace a linear search on a given array, identify the number of comparisons made in best, worst, and average cases, and discuss why it remains the only viable option for unsorted collections.
在AQA考题中，你可能需要追踪给定数组上的线性搜索过程，确定最好、最坏和平均情况下的比较次数，并讨论为什么对于未排序的集合，它仍然是唯一可行的选择。
3. Binary Search: The Divide-and-Conquer Method | 二分搜索：分治法
Binary search is a vastly more efficient algorithm that operates exclusively on sorted data. It takes advantage of the ordering by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the lower half; if greater, it continues in the upper half. This logarithmic reduction means the number of elements to be checked shrinks dramatically with each step.
二分搜索是一种效率高得多的算法，仅适用于已排序的数据。它利用数据的顺序性，反复将搜索区间一分为二。如果目标值小于中间元素，搜索继续在下半部分进行；如果大于，则继续在上半部分进行。这种对数级的缩减意味着每一步需要检查的元素数量都急剧减少。
The algorithm typically maintains two pointers, low and high, which define the current search space. At each iteration, the mid-point is calculated using integer division: mid = (low + high) // 2. If the target matches the element at mid, the search succeeds; otherwise, either low becomes mid + 1 or high becomes mid – 1. The process repeats until the target is found or low exceeds high.
该算法通常维护两个指针low和high，定义当前搜索空间。每次迭代时，使用整数除法计算中点：mid = (low + high) // 2。如果目标与mid处的元素匹配，搜索成功；否则，要么low变为mid + 1，要么high变为mid – 1。此过程重复进行，直到找到目标或low大于high。
The worst-case time complexity of binary search is O(log n), which is exponentially better than linear search for large n. However, the requirement for sorted data means that if the initial data is unsorted, an O(n log n) sorting step must be performed first, potentially negating the advantage for single searches.
二分搜索的最坏情况时间复杂度为O(log n)，对于大的n，这比线性搜索具有指数级的优势。然而，要求数据已排序意味着如果初始数据未排序，必须先执行O(n log n)的排序步骤，这可能会抵消单次搜索的优势。
4. Comparing Linear and Binary Search | 线性搜索与二分搜索的比较
The choice between linear and binary search depends on several factors. The table below summarises their key differences according to the AQA specification.
选择线性搜索还是二分搜索取决于多个因素。下表根据AQA规范总结了它们的主要区别。
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data prerequisite | None (unsorted fine) | Must be sorted |
| Worst-case time | O(n) | O(log n) |
| Best-case time | O(1) | O(1) |
| Space complexity | O(1) | O(1) iterative, O(log n) recursive |
| Typical use | Small datasets, unsorted collections | Large sorted arrays, repeated searches |
In terms of the number of comparisons, for an array of 1,000,000 elements, a linear search might need up to 1,000,000 comparisons, while a binary search requires at most about 20. This illustrates why binary search is preferred when the dataset is static and can be sorted once and queried many times. However, if data is constantly being inserted or deleted, maintaining sorted order may be costly.
就比较次数而言，对于一个包含1,000,000个元素的数组，线性搜索最多可能需要1,000,000次比较，而二分搜索最多只需要大约20次。这说明了为什么在数据集是静态的、可以排序一次并多次查询时，首选二分搜索。然而，如果数据频繁插入或删除，维持有序状态的代价可能很高。
In AQA exam contexts, you should be able to justify your choice of algorithm based on these trade-offs and provide examples of scenarios where each would be appropriate.
在AQA考试情境中，你应能基于这些权衡为算法选择提供理由，并举例说明每种算法适用的场景。
5. Implementation Details in Pseudocode and Python | 伪代码和Python中的实现细节
AQA often requires candidates to write and analyse search algorithms using a generic pseudocode or high-level programming language. For linear search, a typical Python implementation is:
AQA常要求考生使用通用伪代码或高级编程语言编写并分析搜索算法。线性搜索的一个典型Python实现如下：
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
For binary search, the iterative version is frequently examined:
二分搜索的迭代版本常被考查：
def binary_search(arr, target):
low = 0
high = len(arr) – 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid – 1
return -1
Recursive binary search is also part of the specification; you must understand how the call stack grows and how base cases prevent infinite recursion. The recursive version might be presented as:
递归二分搜索也在考纲范围内；你必须理解调用栈如何增长，以及基本情况如何防止无限递归。递归版本可能如下所示：
def binary_search_rec(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search_rec(arr, target, low, mid-1)
else:
return binary_search_rec(arr, target, mid+1, high)
In examinations, attention is often given to off-by-one errors, incorrect mid-point calculations, and missing base cases. Always simulate your code with small test arrays to ensure correctness.
考试中常会关注差一错误、中点计算错误和缺少基本情况等问题。务必用小型测试数组模拟代码以确保其正确性。
6. Searching in Linked Lists | 链表中的搜索
Searching a linked list, whether singly or doubly linked, is inherently sequential because nodes are not stored contiguously in memory. You must start at the head node and follow pointers until the target is found or the end of the list is reached. Consequently, the only available search strategy on a linked list is linear search, giving O(n) time complexity.
在链表中搜索，无论是单向还是双向链表，本质上都是顺序的，因为节点在内存中不是连续存储的。你必须从头节点开始，沿着指针遍历，直到找到目标或达到链表末尾。因此，链表上唯一可用的搜索策略是线性搜索，时间复杂度为O(n)。
AQA may ask you to write an algorithm to search a linked list for a given value. The key operations involve traversing the nodes using a current pointer, and checking the data attribute of each node. Special care must be taken to handle an empty list (head is null) to avoid runtime errors.
AQA可能会要求你编写在链表中搜索给定值的算法。关键操作包括使用current指针遍历节点，并检查每个节点的数据属性。需要特别注意处理空链表（head为null）的情况，以避免运行时错误。
Binary search cannot be applied to linked lists because random access to elements is not possible in constant time. Even if the list is sorted, jumping to the middle element requires O(n) time, negating the benefit of the binary approach.
二分搜索无法应用于链表，因为无法在常数时间内随机访问元素。即使链表已排序，跳转到中间元素也需要O(n)时间，这抵消了二分法的优势。
7. Binary Search Trees and Tree Search | 二叉搜索树与树的搜索
A binary search tree (BST) is a data structure specifically designed to support efficient searching. For any given node, all keys in the left subtree are less than the node’s key, and all keys in the right subtree are greater. This ordering property allows a search to proceed down a path from the root, making a decision at each node analogous to binary search in an array.
二叉搜索树（BST）是一种专门为支持高效搜索而设计的数据结构。对于任意给定节点，左子树中的所有键值都小于该节点的键值，右子树中的所有键值都大于该节点的键值。这种有序性质允许搜索从根节点沿路径向下进行，在每个节点做出决策，类似于数组中的二分搜索。
The search algorithm in a BST is straightforward: start at the root, compare the target with the current node’s key. If equal, return the node; if less, go left; if greater, go right. If a null child is encountered, the target is not in the tree. The efficiency of a BST search depends on the shape of the tree. In a balanced tree, the height is approximately log n, giving O(log n) search time. In the worst case (a degenerate tree resembling a linked list), the height is n, deteriorating to O(n).
BST中的搜索算法很简单：从根节点开始，将目标与当前节点的键值比较。如果相等，返回该节点；如果更小，向左走；如果更大，向右走。如果遇到空子节点，说明目标不在树中。BST搜索的效率取决于树的形状。在平衡树中，高度大约是log n，搜索时间为O(log n)。在最坏情况下（退化成类似链表的树），高度为n，退化为O(n)。
AQA may examine your understanding of how to insert and search in a BST, as well as how tree rotation in self-balancing trees (conceptual treatment) helps maintain O(log n) search times. Understanding tree traversals (pre-order, in-order, post-order) is also relevant, as they are used to visit all nodes but are not search per se.
AQA可能会考查你对BST中插入和搜索操作的理解，以及自平衡树中的树旋转（概念性讨论）如何帮助维持O(log n)的搜索时间。理解树的遍历（先序、中序、后序）也很重要，因为它们用于访问所有节点，但本身并非搜索。
8. Searching in Hash Tables | 哈希表中的搜索
Although hash tables are not explicitly prominent in the AQA fundamentals of algorithms section for searching, they are a vital part of the broader data structures topic. A hash table offers average-case O(1) search time, making it the fastest searching method when implemented correctly. It works by applying a hash function to the key to compute an index into an array of buckets.
尽管哈希表在AQA搜索相关算法基础部分中不是特别突出，但它们是更广泛的数据结构主题中的重要部分。哈希表提供平均情况O(1)的搜索时间，使其在正确实现时成为最快的搜索方法。其原理是对键应用哈希函数，计算出桶数组的索引。
The search process involves hashing the target key, accessing that bucket, and then potentially searching a small chain (in chaining) or probing sequentially (in open addressing) to find the exact record. Understanding collision resolution techniques, such as chaining and linear probing, can help you appreciate the trade-offs between memory usage and performance.
搜索过程包括对目标键进行哈希处理，访问对应的桶，然后可能需要在短链中搜索（链接法）或顺序探测（开放寻址法）以找到确切记录。理解冲突解决技术，如链接法和线性探测，有助于你理解内存使用和性能之间的权衡。
In AQA exam questions, you might be asked to compare the efficiency of searching with different data structures, and hash tables will often come up as the optimal choice for search-intensive applications where memory is not severely constrained.
在AQA考题中，你可能会被要求比较不同数据结构的搜索效率，而哈希表通常会被认为是内存限制不严格时搜索密集型应用的最佳选择。
9. Searching in Files and External Storage | 文件和外部存储中的搜索
When data resides on secondary storage, searching poses additional challenges because disk access is orders of magnitude slower than RAM. The AQA specification acknowledges sequential file search and binary search on sorted files. For sequential access files, only linear search is possible, and it may be inefficient for very large files.
当数据存储在二级存储器上时，搜索带来额外挑战，因为磁盘访问比RAM慢几个数量级。AQA考纲认可顺序文件搜索和在已排序文件上的二分搜索。对于顺序访问文件，只能使用线性搜索，对于非常大的文件可能效率低下。
Direct access storage means binary search can be applied to sorted files, as the mid-record can be jumped to directly. However, practical systems often use index structures like B-trees to speed up file searching. While in-depth knowledge of B-trees is beyond the core AQA search algorithms topic, you should be aware that indexing is a common technique to reduce search time on large volumes of data.
直接访问存储意味着可以对已排序文件应用二分搜索，因为可以直接跳转到中间记录。然而，实际系统常使用B树等索引结构来加速文件搜索。虽然B树的深入知识超出了核心AQA搜索算法主题，但你应该知道索引是减少大数据量搜索时间的常见技术。
Exam questions may ask you to describe the steps of searching a file or to evaluate the appropriateness of a search algorithm given a particular storage medium and file organisation.
考题可能会要求你描述搜索文件的步骤，或根据特定的存储介质和文件组织结构评估搜索算法的适当性。
10. Algorithmic Complexity and Big O Notation | 算法复杂度与大O记法
A thorough grasp of Big O notation is essential for comparing searching algorithms. The AQA specification expects you to express the worst-case time complexity of linear search as O(n) and binary search as O(log n). You should also understand that constant factors are dropped, so O(2n) simplifies to O(n).
深入理解大O记法对于比较搜索算法至关重要。AQA考纲希望你能够将线性搜索的最坏情况时间复杂度表示为O(n)，二分搜索表示为O(log n)。你还应理解常数因子被忽略，因此O(2n)简化为O(n)。
The complexity class O(log n) derives from the fact that the problem size is halved at each step. The number of times n can be halved before reaching 1 is log₂ n. For a dataset of size 1,000,000, log₂ 1,000,000 ≈ 20, which means binary search takes at most 20 comparisons. This is a drastic improvement over linear search.
O(log n)复杂度类别源于每一步问题规模减半这一事实。在达到1之前，n可以被折半的次数是log₂ n。对于大小为1,000,000的数据集，log₂ 1,000,000 ≈ 20，这意味着二分搜索最多需要20次比较。这相对于线性搜索是巨大的改进。
Be prepared to deduce the complexity from a given algorithm, identify best and worst cases, and explain why the average case for linear search is also O(n) (target equally likely to be anywhere), while binary search remains O(log n) on average for random targets.
做好准备，能够从给定算法中推导出复杂度，识别最好和最坏情况，并解释为什么线性搜索的平均情况也是O(n)（目标等可能地在任何位置），而对于随机目标，二分搜索的平均情况仍然是O(log n)。
11. Common Exam Traps and How to Avoid Them | 常见考试陷阱及如何避免
Many candidates lose marks on search algorithm questions due to minor but critical mistakes. The most frequent errors include: forgetting to update low and high pointers correctly in binary search (using mid instead of mid±1), using invalid mid-point formulas that cause integer overflow (though rarely a concern in pseudocode, the principle matters), and failing to handle the “not found” condition.
许多考生在搜索算法题上失分是由于微小但关键的错误。最常见的错误包括：在二分搜索中忘记正确更新low和high指针（使用mid而非mid±1），使用导致整数溢出的中点公式（尽管在伪代码中很少关注，但原理很重要），以及未能处理“未找到”的情况。
Another common pitfall is attempting to apply binary search to an unsorted array. The algorithm will fail to find the target even if it is present, because its logic relies on the ordering assumption. Always check whether the data is explicitly stated as sorted before choosing your algorithm.
另一个常见陷阱是试图对未排序的数组应用二分搜索。即使目标存在，该算法也无法找到它，因为它的逻辑依赖于排序假设。在选择算法之前，务必先检查数据是否明确说明为已排序。
When tracing recursive binary search, be careful to show the changing values of low and high on the call stack; a typical AQA mark scheme awards marks for correctly updating the bounds and identifying the base case. For linear search, students sometimes forget the possibility of duplicate values—a standard linear search returns the first occurrence; clarify whether this is acceptable.
在追踪递归二分搜索时，要注意显示调用栈上low和high值的变化；典型的AQA评分方案会为正确更新边界和识别基本情况而给分。对于线性搜索，学生有时会忘记重复值的可能性——标准线性搜索返回第一个匹配项；应阐明这是否符合要求。
12. Exam-Style Questions and Practice | 考试风格题目与练习
To consolidate your understanding, consider this typical AQA question: “An array contains the integers [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Show the steps of a binary search for the value 23.” Your answer should clearly list the values of low, high, and mid at each iteration, the comparison result, and the final index returned.
为了巩固理解，请思考以下典型AQA题目：“一个数组包含整数[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]。展示对值23进行二分搜索的步骤。”你的答案应清晰列出每次迭代中low、high和mid的值、比较结果以及返回的最终索引。
You may also be asked to write an algorithm that searches an array of product codes for a specific code and returns a Boolean. Practice implementing both linear and binary search using pseudocode and the high-level language you are studying. Pay special attention to input validation and edge cases: empty collection, target smaller than first element, target larger than last element.
你可能还会被要求编写一个算法，在商品代码数组中搜索特定代码并返回布尔值。练习使用伪代码和你所学的高级语言实现线性搜索和二分搜索。特别注意输入验证和边界情况：空集合、目标小于第一个元素、目标大于最后一个元素。
Additionally, comparative essay-style questions might ask: “Discuss the factors that influence the choice between linear search and binary search in a real-world application.” Here, you need to consider frequency of searches, volatility of the data, memory constraints, and the cost of maintaining sorted order.
此外，比较类的小论文式问题可能会问：“讨论在实际应用中影响线性搜索和二分搜索选择的因素。”这里你需要考虑搜索频率、数据的易变性、内存限制以及维护有序状态的代价。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导