📚 Searching Algorithms for IB Edexcel Computer Science | IB Edexcel 计算机：搜索 考点精讲
Searching is a fundamental operation in computer science, allowing programs to locate specific data within a collection. For IB and Edexcel Computer Science, understanding search algorithms, their implementation, and efficiency is crucial for both exams and practical programming tasks. This revision guide covers linear search, binary search, searching in data structures like binary search trees and hash tables, along with complexity analysis and common pitfalls.
搜索是计算机科学中的基本操作，程序通过它从数据集合中定位特定的元素。对于 IB 和 Edexcel 计算机科学课程而言，理解搜索算法、实现方式以及效率，对于考试和实际编程任务都至关重要。本考点精讲涵盖线性搜索、二分搜索、以及在二叉搜索树和哈希表等数据结构中的搜索，同时包括复杂度分析和常见错误。
1. What is Searching? | 什么是搜索？
Searching refers to the process of finding a target value within a data structure, such as an array, list, tree, or hash table. The algorithm returns the position of the target or a Boolean indicating presence. The choice of search method depends on the data structure and whether the data is sorted.
搜索是指在数组、列表、树或哈希表等数据结构中查找目标值的过程。算法返回目标的位置或一个布尔值表示是否存在。搜索方法的选择取决于数据结构以及数据是否已排序。
2. Linear Search Algorithm | 线性搜索算法
Linear search, also known as sequential search, examines each element one by one from the beginning until the target is found or the end is reached. It works on both sorted and unsorted data. The algorithm is straightforward to implement using a loop.
线性搜索又称顺序搜索，它从头开始逐个检查每个元素，直到找到目标或到达末尾。该算法在排序和未排序的数据上均可工作，使用循环实现非常简单。
3. Linear Search Example & Complexity | 线性搜索示例与复杂度
Consider an array [8, 4, 9, 3, 7]. To find 3, linear search compares 8, 4, 9, and finally 3 at index 3. In the worst case, it checks all n elements. Thus, time complexity is O(n). Space complexity is O(1) as it uses only a few variables.
考虑数组 [8, 4, 9, 3, 7]。要查找 3，线性搜索依次比较 8、4、9，最后在索引 3 处找到 3。最坏情况下需要检查全部 n 个元素。因此，时间复杂度为 O(n)。空间复杂度为 O(1)，因为它只使用少量变量。
4. Binary Search Algorithm | 二分搜索算法
Binary search is a divide-and-conquer algorithm that requires the data to be sorted. It repeatedly divides the search interval in half by comparing the target with the middle element. If the target is smaller, the search continues in the left half; otherwise, in the right half. This process continues until the target is found or the interval is empty.
二分搜索是一种分治算法，要求数据已经排序。它通过将目标与中间元素比较，反复将搜索区间减半。如果目标较小，则继续在左半部分搜索；否则在右半部分搜索。该过程持续直到找到目标或区间为空。
5. Binary Search Requirements & Implementation | 二分搜索的要求与实现
For binary search to work correctly, the data must be sorted in ascending (or descending) order. The algorithm typically uses three pointers: low, high, and mid. In each iteration, mid = low + (high – low) / 2. The target is compared with arr[mid]. If equal, the index is returned. If target is less, high = mid – 1; else low = mid + 1. It can be implemented both iteratively and recursively.
二分搜索要正确工作，数据必须按升序（或降序）排列。该算法通常使用三个指针：low、high 和 mid。在每次迭代中，mid = low + (high – low) / 2。将目标与 arr[mid] 比较。若相等则返回索引。若目标较小，则 high = mid – 1；否则 low = mid + 1。它可以用迭代和递归两种方式实现。
6. Binary Search Complexity & Performance | 二分搜索的复杂度与性能
Each step halves the search space, so the maximum number of comparisons is log2n. Time complexity is O(log n), which is significantly better than O(n) for large datasets. Space complexity is O(1) for iterative version and O(log n) for recursive due to call stack.
每一步都将搜索范围减半，因此最大比较次数为 log2n。时间复杂度为 O(log n)，对于大数据集来说远优于 O(n)。迭代版本的空间复杂度为 O(1)，而递归版本由于调用栈为 O(log n)。
7. Comparison: Linear vs Binary Search | 比较：线性搜索与二分搜索
| Aspect | Linear Search | Binary Search |
|---|---|---|
| Data requirement | Unsorted or sorted | Must be sorted |
| Time complexity | O(n) | O(log n) |
| Best case | O(1) (first element) | O(1) (middle element) |
| Space | O(1) | O(1) or O(log n) |
| Use case | Small datasets, linked lists | Large sorted arrays |
Choosing between them depends on whether the data is sorted and the size of the dataset. For unsorted or frequently updated lists, linear search is simpler; for large static sorted arrays, binary search is far more efficient.
选择哪种搜索取决于数据是否排序以及数据集大小。对于未排序或频繁更新的列表，线性搜索更简单；对于大型静态有序数组，二分搜索效率高得多。
8. Searching in Data Structures: Binary Search Tree | 数据结构中的搜索：二叉搜索树
A binary search tree (BST) stores keys in a way that enables fast searching. For any node, all keys in the left subtree are smaller and all keys in the right subtree are larger. To search for a key, compare it with the root. If smaller, go left; if larger, go right; if equal, found. This recursive process continues until a null reference is reached.
二叉搜索树 (BST) 通过一种能够实现快速搜索的方式存储键值。对于任意结点，左子树中的所有键值都较小，右子树中的所有键值都较大。要搜索一个键值，将其与根结点比较。若较小则向左，若较大则向右，若相等则找到。该递归过程持续直到到达空引用。
9. BST Search Complexity & Balance | BST 搜索复杂度与平衡
In the best case, the tree is balanced, giving a search time of O(log n). In the worst case, the tree degenerates into a linked list (e.g., inserting sorted data without balancing), making search O(n). Self-balancing trees like AVL or Red-Black trees maintain O(log n) search time by rotating nodes on insertion and deletion.
在最佳情况下，树是平衡的，搜索时间为 O(log n)。在最坏情况下，树退化为链表（例如，插入已排序数据而不进行平衡调整），搜索变为 O(n)。像 AVL 树或红黑树这样的自平衡树通过在插入和删除时旋转结点来保持 O(log n) 的搜索时间。
10. Searching in Hash Tables | 哈希表中的搜索
A hash table provides near O(1) average search time. It uses a hash function to map a key to an index in an array. When searching, the same hash function computes the index, and the key is compared at that bucket. Collisions are handled by chaining or open addressing, which can increase search time slightly.
哈希表提供接近 O(1) 的平均搜索时间。它使用哈希函数将键映射到数组中的索引。搜索时，同一哈希函数计算出索引，并在该桶中比较键。冲突通过链表法或开地址法处理，可能会略微增加搜索时间。
11. Common Exam Pitfalls | 常见考试陷阱
Students often forget that binary search requires sorted data. They may misuse the midpoint formula, especially with integer overflow or off-by-one errors. In pseudocode, failing to update low and high correctly leads to infinite loops. Also, confusing best-case and worst-case complexities for linear and binary search loses marks.
学生经常忘记二分搜索要求数据已排序。他们可能误用中点公式，尤其是整数溢出或差一错误。在伪代码中，未能正确更新 low 和 high 会导致无限循环。此外，混淆线性搜索和二分搜索的最佳与最坏情况复杂度也会失分。
12. Exam-style Questions & Tips | 考题风格与技巧
Typical IB/Edexcel questions ask to trace binary search on an array, write pseudocode for linear/binary search, compare efficiencies, or explain BST search. Practice dry-running algorithms with small datasets. Memorize the logarithmic equation: if n=1024, log21024 = 10, illustrating O(log n) advantage. For BST questions, draw the tree and show each comparison step clearly.
典型的 IB/Edexcel 考题要求跟踪二分搜索在数组上的执行过程、为线性/二分搜索编写伪代码、比较效率或解释 BST 搜索。练习在小数据集上模拟算法执行。记住对数方程：若 n=1024，log21024 = 10，体现了 O(log n) 的优势。对于 BST 问题，画出树并清晰展示每一步比较过程。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply