📚 IB Computer Science: Searching Algorithms Exam Essentials | IB 计算机：搜索考点精讲
Searching is a fundamental operation in computer science. Whether you are looking up a contact in your phone, finding a keyword in a document, or querying a database, efficient search algorithms are essential. In the IB Computer Science curriculum, students are expected to understand and analyse linear search, binary search, and searching within data structures such as binary search trees. This revision guide covers all key points you need for the exam.
搜索是计算机科学中的基本操作。无论是查找手机联系人、在文档中搜索关键字，还是查询数据库，高效的搜索算法都至关重要。在 IB 计算机科学课程中，学生需要理解并分析线性搜索、二分搜索，以及在二叉搜索树等数据结构中进行搜索。本复习指南涵盖考试所需的所有重点。
1. Overview of Searching Algorithms | 搜索算法概述
A search algorithm retrieves a specific element from a collection of data. The efficiency depends on how the data is organised. For the IB syllabus, you must know linear search and binary search for arrays, and search operations in a binary search tree. Understanding these algorithms helps in analysing their time complexity and selecting the right one for a given situation.
搜索算法从数据集合中检索特定元素。其效率取决于数据的组织方式。根据 IB 大纲，你需要掌握数组的线性搜索和二分搜索，以及二叉搜索树中的搜索操作。理解这些算法有助于分析它们的时间复杂度，并在特定情境下选择正确的算法。
2. Linear Search (Sequential Search) | 线性搜索（顺序搜索）
Linear search examines each element of an array one by one until the target value is found or the end is reached. It does not require the data to be sorted and works on any list. The algorithm starts at index 0, compares the current element with the target, and moves to the next index on mismatch.
线性搜索逐个检查数组中的每个元素，直到找到目标值或到达末尾。它不要求数据有序，适用于任何列表。算法从索引 0 开始，将当前元素与目标比较，不匹配则移动到下一个索引。
Best case: the target is at the first position, giving O(1). Worst case: the target is at the end or absent, requiring n comparisons, giving O(n). Average case also O(n). This algorithm is simple but inefficient for large datasets.
最好情况：目标位于第一个位置，时间复杂度为 O(1)。最坏情况：目标在末尾或不存在，需要 n 次比较，时间复杂度为 O(n)。平均情况也是 O(n)。该算法简单，但对于大数据集效率低。
Time Complexity: O(n)
3. Binary Search Algorithm | 二分搜索算法
Binary search operates on a sorted array. It repeatedly divides the search interval in half. If the target value equals the middle element, the search ends. If the target is less, the search continues in the left half; otherwise, it proceeds in the right half. This process continues until the target is found or the interval is empty.
二分搜索应用于已排序数组。它反复将搜索区间分成两半。若目标值等于中间元素，则搜索结束。若目标较小，则在左半部分继续搜索；否则在右半部分继续。重复此过程，直到找到目标或区间为空。
For example, to search 23 in [5, 12, 17, 23, 29, 34, 41], first compare 23 with the middle (23), match found. The efficiency is logarithmic because the search space is halved each step.
例如在数组 [5, 12, 17, 23, 29, 34, 41] 中搜索 23，首先将 23 与中间元素 23 比较，匹配成功。其效率是对数级的，因为每一步搜索范围减半。
Time Complexity: O(log n)
4. Recursive Binary Search | 递归二分搜索
Binary search can be implemented recursively. The recursive approach checks the middle element and, if not found, calls itself with the appropriate sub-array. The base case occurs when the low index exceeds the high index, meaning the target is absent.
二分搜索可以用递归实现。递归方法检查中间元素，如果没找到，则用适当的子数组调用自身。基本情况发生在低位索引超过高位索引时，意味着目标不存在。
The recurrence relation is T(n) = T(n/2) + O(1). Solving this using the Master Theorem or by inspection gives T(n) = O(log n). IB exams may ask you to trace a recursive binary search call stack.
其递推关系为 T(n) = T(n/2) + O(1)。使用主定理或直接推导可得 T(n) = O(log n)。IB 考试可能会要求你追踪递归二分搜索的调用栈。
5. Comparing Linear and Binary Search | 线性搜索与二分搜索的比较
The table below summarises the differences between the two fundamental search algorithms. Understanding these distinctions is crucial for choosing the most appropriate method in a given scenario.
下表总结了两种基本搜索算法的差异。理解这些区别对于在特定场景中选择最合适的方法至关重要。
| Property | Linear Search | Binary Search |
|---|---|---|
| Data requirement | Unsorted or sorted | Must be sorted |
| Worst-case time | O(n) | O(log n) |
| Best-case time | O(1) | O(1) |
| Implementation | Simple loop | Loop or recursion |
| Data structure | Array, list | Array (random access) |
对应中文比较：线性搜索不需要排序，最坏情况 O(n)，实现简单；二分搜索必须有序，最坏情况 O(log n)，但对数据结构有随机访问要求。
6. Searching in a Binary Search Tree (BST) | 二叉搜索树 (BST) 中的搜索
A BST organises data so that for any node, left subtree values are less, and right subtree values are greater. To search for a key, you start at the root and compare the key with the node’s value. If equal, you have found it. If the key is smaller, go left; if larger, go right. This process repeats recursively or iteratively.
二叉搜索树的数据组织方式为：对于任一节点，左子树的值均小于该节点值，右子树的值均大于该节点值。搜索一个键值时，从根节点开始，将键值与节点值比较。若相等则找到；若键值较小则向左走，较大则向右走。此过程递归或迭代重复。
In a balanced BST, the height is about log₂ n, so search takes O(log n). However, if the tree is unbalanced (e.g., all nodes inserted in sorted order), it degenerates into a linked list, and search becomes O(n). Self-balancing trees like AVL or Red-Black trees maintain O(log n) searches. IB expects you to understand these time complexities.
在平衡的 BST 中，树高约为 log₂ n，因此搜索时间复杂度为 O(log n)。但如果树不平衡（如所有节点按排序顺序插入），它会退化为链表，搜索复杂度变为 O(n)。自平衡树如 AVL 或红黑树能保持 O(log n) 的搜索性能。IB 要求你理解这些时间复杂度。
7. Tree Traversals as Search Methods | 树遍历作为搜索方法
Tree traversals are procedures for visiting every node in a tree exactly once. In the IB context, inorder, preorder, and postorder traversals can be seen as systematic ways to search through all elements of a tree. For instance, inorder traversal of a BST visits nodes in sorted order, effectively performing a complete ‘search’ of all values.
树遍历是恰好访问树中每个节点一次的过程。在 IB 语境中，中序、前序和后序遍历可以被视为系统地搜索树中所有元素的方式。例如，BST 的中序遍历按排序顺序访问节点，实际上是对所有值进行了一次完整的“搜索”。
These traversals are not used for finding a specific key quickly, but they underpin many algorithms, including expression tree evaluation and serialising a tree. You should be able to trace and code recursive traversals, which reinforces recursive thinking essential for binary search.
这些遍历并非用于快速查找特定键值，但它们是许多算法的基础，包括表达式树求值和树的序列化。你应该能够追踪并编写递归遍历代码，这能强化二分搜索所需的递归思维。
8. Efficiency and Big O of Search Algorithms | 搜索算法的效率与大 O 表示
Big O notation describes the upper bound of an algorithm’s running time. For search algorithms, we measure the number of comparisons as a function of input size n. Linear search has a linear relationship, so it is O(n). Binary search demonstrates logarithmic behaviour, O(log n). The table below shows typical complexities.
大 O 表示法描述了算法运行时间的上限。对于搜索算法，我们以输入规模 n 的函数来衡量比较次数。线性搜索呈线性关系，因此为 O(n)。二分搜索表现出对数行为，为 O(log n)。下表显示了典型的复杂度。
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) |
| Binary Search | O(1) | O(log n) | O(log n) |
| BST Search (balanced) | O(1) | O(log n) | O(log n) |
| BST Search (unbalanced) | O(1) | O(n) | O(n) |
For IB exams, always reason about the worst-case scenario unless asked otherwise. Also note that binary search requires random access, typically on arrays, while BST search uses pointers.
在 IB 考试中，除非另有说明，总应从最坏情况进行分析。还需注意二分搜索需要随机访问，通常在数组上实现，而 BST 搜索使用指针。
9. Real-world Applications of Searching | 搜索算法的实际应用
Search algorithms are everywhere. Databases use indexes built on B-trees (a generalisation of BST) for rapid record lookups. Operating systems search file directories. Network routers search routing tables using algorithms like longest prefix match. Spell checkers employ search strategies in a dictionary trie or hash table.
搜索算法无处不在。数据库使用基于 B 树（BST 的一般化形式）的索引来快速查找记录。操作系统搜索文件目录。网络路由器使用最长前缀匹配等算法搜索路由表。拼写检查器在字典树或哈希表中运用搜索策略。
In the IB context, understanding linear and binary search helps you appreciate why data organisation matters. For instance, a phone book is effective because it is sorted, enabling you to employ a binary search approach mentally. Similarly, an unsorted list of student names requires a linear scan.
在 IB 语境下，理解线性搜索和二分搜索能帮助你认识到数据组织的重要性。例如，电话簿之所以高效正是因为它已排序，使得你可以下意识地使用二分搜索方法。同样，未排序的学生名单则需要线性扫描。
10. Summary and Exam Tips | 总结与考试建议
Make sure you can manually simulate binary search on a small array and calculate the number of comparisons. Be mindful of mid index calculation: mid = low + (high – low) // 2 to avoid overflow in some languages, though IB pseudocode accepts (low + high) DIV 2. Always check that the array is sorted before applying binary search.
务必确保能手在小数组上手动模拟二分搜索，并计算比较次数。注意中间索引的计算：mid = low + (high – low) // 2 在某些语言中可以避免溢出，不过 IB 伪代码接受 (low + high) DIV 2。应用二分搜索前务必检查数组是否已排序。
Watch out for off-by-one errors in boundary conditions. For BST search, visualise the tree and trace the path. In recursive algorithms, identify the base case and ensure it is reached. Finally, link the concept of divide and conquer to binary search; it is a classic example you can reference in Paper 1 and Paper 2.
小心边界条件中的差一错误。对于 BST 搜索，可视化树并追踪路径。在递归算法中，识别基本情况并确保能够达到。最后，将分而治之的概念与二分搜索联系起来；这是你在 Paper 1 和 Paper 2 中都可以引用的经典例子。
Binary Search = Divide & Conquer → O(log n)
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