Search Algorithms for IB & CIE CS | IB与CIE计算机搜索算法考点精讲

📚 Search Algorithms for IB & CIE CS | IB与CIE计算机搜索算法考点精讲

Searching is a fundamental operation in computer science that underpins everything from database queries to web indexing. For IB and CIE Computer Science students, understanding the mechanics, efficiency, and limitations of core search algorithms is essential for both theory papers and practical problem-solving. This article explores the key searching techniques you need to master, including linear search, binary search, and their associated complexities and applications.

搜索是计算机科学中的一项基础操作，支撑着从数据库查询到网页索引的各种应用。对于 IB 和 CIE 计算机科学学生而言，理解核心搜索算法的机制、效率和局限性，对理论考试和实际问题解决都至关重要。本文将深入探讨你需要掌握的关键搜索技术，包括线性搜索、二分搜索，以及它们相关的复杂度和应用场景。

1. What is a Search Algorithm? | 什么是搜索算法？

A search algorithm is a step-by-step procedure used to locate a specific item (often called a target or key) within a collection of data, typically held in an array, list, or other data structure. The goal is to return the position of the item or an indication that it is not present.

搜索算法是一种逐步执行的过程，用于在数据集合（通常保存在数组、列表或其他数据结构中）中定位特定项（通常称为目标或关键字）。其目标是返回该项的位置，或者指出它不存在。

Essential terminology includes the search space (the entire dataset), the target (the value being searched for), and the outcome (index found or a sentinel value like -1).

基本术语包括搜索空间（整个数据集）、目标（正在搜索的值）以及结果（找到的索引或类似 -1 的哨兵值）。

2. Linear Search (Sequential Search) | 线性搜索（顺序搜索）

Linear search inspects each element of the list one by one, starting from the first element, until the target is found or the end of the list is reached. It works on any list, whether sorted or unsorted.

线性搜索从第一个元素开始，逐个检查列表中的每个元素，直到找到目标或到达列表末尾。它适用于任何列表，无论是否排序。

In pseudocode for an array A of N elements with target T:

Set i = 0
While i < N and A[i] ≠ T: increment i
If i < N return i, else return -1

数组 A 有 N 个元素，目标为 T 的伪代码：

设置 i = 0
当 i < N 且 A[i] ≠ T 时：递增 i
若 i < N 则返回 i，否则返回 -1

3. Time Complexity of Linear Search | 线性搜索的时间复杂度

The worst-case time complexity of linear search is O(N), where N is the number of elements. This occurs when the target is at the very end of the list or not present at all. The best case is O(1) if the target is found at the first position. The average case also leads to O(N) because, on average, you inspect half the elements.

线性搜索的最坏情况时间复杂度是 O(N)，其中 N 是元素个数。当目标正好在列表末尾或根本不存在时，就会出现这种情况。如果目标在第一个位置就被找到，最好情况是 O(1)。平均情况也是 O(N)，因为平均而言要检查一半的元素。

In IB and CIE exams, you are expected to trace linear search and calculate its step count. A typical CIE Paper 4 question may ask you to write an iterative linear search function and discuss its inefficiency on large datasets.

在 IB 和 CIE 考试中，你需要追踪线性搜索的执行过程并计算步数。典型的 CIE Paper 4 问题可能会要求你写一个迭代的线性搜索函数，并讨论它在大型数据集上的低效之处。

4. Binary Search | 二分搜索

Binary search dramatically reduces search time by repeatedly dividing the search interval in half. It requires the data to be sorted in ascending (or descending) order. The algorithm compares the target with the middle element and decides to continue searching in either the left or right half.

二分搜索通过反复将搜索区间减半，大幅缩短搜索时间。它要求数据按升序（或降序）排序。算法将目标与中间元素进行比较，决定是在左半部分还是右半部分继续搜索。

The steps are:

Set low = 0, high = N-1.
While low ≤ high: compute mid = (low + high) / 2 (integer division).
If A[mid] == target, return mid.
If A[mid] < target, set low = mid + 1.
Else set high = mid – 1.
If the loop ends without returning, the target is not present; return -1.

步骤如下：

设置 low = 0，high = N-1。
当 low ≤ high 时：计算 mid = (low + high) / 2（整数除法）。
如果 A[mid] == 目标，返回 mid。
如果 A[mid] < 目标，设置 low = mid + 1。
否则设置 high = mid – 1。
若循环结束未返回，则目标不存在；返回 -1。

5. Time Complexity of Binary Search | 二分搜索的时间复杂度

Binary search exhibits a logarithmic time complexity of O(log N) in the worst and average cases. Each iteration halves the search space, so for a list of size 1024, it takes at most 10 comparisons. Best case is O(1) when the middle element is the target.

二分搜索在最坏和平均情况下表现出对数时间复杂度 O(log N)。每次迭代将搜索空间减半，因此对于大小为 1024 的列表，最多需要 10 次比较。当中间元素就是目标时，最好情况为 O(1)。

The logarithmic behaviour is formally derived from the recurrence relation T(N) = T(N/2) + O(1). IB syllabus explicitly requires you to understand and explain why binary search is O(log N) and contrast it with linear search.

对数行为可以从递推关系 T(N) = T(N/2) + O(1) 正式推导。IB 大纲明确要求你理解并解释为什么二分搜索是 O(log N)，并与线性搜索进行对比。

6. Recursive Implementation of Binary Search | 二分搜索的递归实现

Binary search can be expressed elegantly via recursion. The function takes low and high indices as parameters and calls itself with a narrowed range until the base case (low > high or target found) is met. This topic is frequently examined in CIE P4 to test recursion and search understanding.

二分搜索可以通过递归优雅地表达。该函数将 low 和 high 索引作为参数，并使用缩小的范围调用自身，直到满足基本情况（low > high 或找到目标）。这是 CIE P4 常考内容，用以测试递归和搜索理解。

Pseudocode for recursive binary search:

FUNCTION recBinarySearch(A, low, high, target)
    IF low > high THEN
        RETURN -1
    ENDIF
    mid = (low + high) DIV 2
    IF A[mid] == target THEN
        RETURN mid
    ELSEIF A[mid] < target THEN
        RETURN recBinarySearch(A, mid+1, high, target)
    ELSE
        RETURN recBinarySearch(A, low, mid-1, target)
    ENDIF
END FUNCTION

递归二分搜索的伪代码：

FUNCTION recBinarySearch(A, low, high, target)
    IF low > high THEN
        RETURN -1
    ENDIF
    mid = (low + high) DIV 2
    IF A[mid] == target THEN
        RETURN mid
    ELSEIF A[mid] < target THEN
        RETURN recBinarySearch(A, mid+1, high, target)
    ELSE
        RETURN recBinarySearch(A, low, mid-1, target)
    ENDIF
END FUNCTION

7. Preconditions and Limitations | 前提条件与局限性

Binary search is powerful but comes with a strict precondition: the list must be sorted. If the dataset is unsorted, a linear search must be used unless you sort first. Sorting itself costs at least O(N log N), so sorting merely for one search is not efficient. However, if multiple searches are performed on the same data, sorting once and then using binary search is beneficial.

二分搜索功能强大，但有一个严格的前提条件：列表必须排序。如果数据集未排序，则必须使用线性搜索，除非先进行排序。排序本身的成本至少为 O(N log N)，因此仅为了单次搜索而排序并不高效。然而，如果要在同一数据上执行多次搜索，先排序一次再使用二分搜索是有益的。

Another limitation is that binary search only works on random-access data structures like arrays. It cannot be directly applied to linked lists without extra cost.

另一个局限性是，二分搜索仅适用于数组等随机访问数据结构。它无法在没有额外成本的情况下直接应用于链表。

8. Searching in Linked Lists vs Arrays | 链表与数组中的搜索

In an array, both linear and binary searches are possible (if sorted). In a singly linked list, linear search is the natural fit, sequentially following the 'next' pointers. Binary search is impractical on linked lists because you cannot jump to the middle element in O(1) time; you would need to traverse from the head, negating the efficiency gain.

在数组中，线性搜索和二分搜索都可以使用（如果排序）。在单链表中，线性搜索是自然匹配的，它依次跟随“next”指针。二分搜索在链表上不切实际，因为你无法在 O(1) 时间内跳转到中间元素；你需要从头部遍历，这会抵消效率提升。

CIE material sometimes asks you to compare searching across these data structures, highlighting that the underlying representation influences algorithm choice.

CIE 的教材有时会要求你比较这些数据结构中的搜索，强调底层表示方式会影响算法选择。

9. Searching in Strings | 字符串搜索

While the above focus on searching for a single value, string searching involves finding a substring (pattern) within a larger string (text). Brute-force string matching uses a sliding window of length M (pattern) over the text of length N, checking character by character, leading to O(N×M) worst-case complexity.

虽然上述内容侧重于搜索单个值，但字符串搜索涉及在较大的字符串（文本）中查找子串（模式）。朴素的字符串匹配使用长度为 M（模式）的滑动窗口在长度为 N 的文本上逐个字符检查，最坏情况复杂度为 O(N×M)。

IB Computer Science includes the concept of pattern matching as an application of searching algorithms, often tied to the computational thinking theme.

IB 计算机科学将模式匹配作为搜索算法的应用概念纳入课程，通常与计算思维主题相关联。

10. Common Exam Question Types | 常见考试题型

IB Paper 1 and CIE Paper 3 often present a sequence of search steps and ask students to identify the algorithm (linear vs binary) based on the trace. Questions may also involve calculating the maximum number of comparisons needed for binary search on a list of 2^k elements.

IB Paper 1 和 CIE Paper 3 经常展示一系列搜索步骤，要求学生根据执行轨迹识别算法（线性还是二分）。问题还可能涉及计算在包含 2^k 个元素的列表上进行二分搜索所需的最大比较次数。

In CIE Paper 4 (practical programming), you must implement both linear and binary search functions, handle edge cases such as empty arrays, and demonstrate testing with appropriate data. IB HL also expects recursive solutions and analysis of space complexity due to call stack usage.

在 CIE Paper 4（实践编程）中，你必须实现线性搜索和二分搜索函数，处理如空数组等边界情况，并用合适的数据进行测试。IB HL 也期待递归解决方案，并分析因调用栈使用而产生的空间复杂度。

11. Space Complexity Considerations | 空间复杂度考量

Linear search and iterative binary search both use O(1) extra space, as they only require a few index variables. Recursive binary search, however, uses O(log N) space on the call stack for the recursive calls, which could be a concern in memory-constrained environments.

线性搜索和迭代二分搜索都只使用 O(1) 额外空间，因为它们只需几个索引变量。然而，递归二分搜索会在调用栈上占用 O(log N) 空间，在内存受限环境中可能是一个问题。

In IB, you may be asked to recommend an iterative over a recursive solution based on space efficiency, especially for large N.

在 IB 中，你可能会被要求基于空间效率推荐迭代解决方案而非递归，特别是对于较大的 N。

12. Summary and Study Tips | 总结与学习建议

To excel in search algorithm questions, build a strong intuition by hand-tracing algorithms on small arrays. Understand the asymptotic notation thoroughly: O(1), O(log N), O(N). Practice converting pseudocode to working Python or Java programs. For binary search, always ensure you handle the index calculation correctly to avoid infinite loops (e.g., by using integer division and proper low/high updates).

要在搜索算法题目中表现出色，通过在小数组上手动追踪算法来建立强大直觉。透彻理解渐进符号：O(1)、O(log N)、O(N)。练习将伪代码转换为可运行的 Python 或 Java 程序。对于二分搜索，务必确保正确处理索引计算，避免无限循环（例如，使用整数除法和正确的 low/high 更新）。

Remember the key differentiator: linear search for unsorted or small data, binary search for large, sorted, random-access data. Mastering search is a gateway to understanding more advanced algorithms and data structures.

记住关键区别：线性搜索适用于未排序或小规模数据，二分搜索适用于大规模、排序、可随机访问的数据。掌握搜索是理解更高级算法和数据结构的大门。

Published by TutorHao | IB & CIE Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Search Algorithms for IB & CIE CS | IB与CIE计算机搜索算法考点精讲