Binary Search | 二分查找

📚 Binary Search | 二分查找

Binary search is a fundamental searching algorithm in A-Level Computer Science that finds the position of a target value within a sorted list. It repeatedly halves the search space, which makes it far more efficient than linear search for large data sets.

二分查找是 A-Level 计算机科学中的一种基础搜索算法，用于在有序列表中查找目标值的位置。它不断将搜索范围减半，因此在大型数据集上比线性查找高效得多。

---

1. What is Binary Search? | 什么是二分查找？

Binary search is an algorithm that locates a target item in a sorted array or list by comparing the target with the middle element. If the middle element matches the target, the search stops. Otherwise the algorithm decides whether to continue searching in the left half or the right half.

二分查找是一种通过在有序数组或列表中将目标值与中间元素进行比较来定位目标项的算法。如果中间元素与目标值匹配，则搜索停止；否则算法决定继续在左半部分还是右半部分中搜索。

Unlike linear search, binary search does not examine every element from the beginning. It exploits the sorted order to discard half of the remaining elements after each comparison.

与线性查找不同，二分查找不会从头开始检查每个元素。它利用有序性，在每次比较后舍弃剩余元素的一半。

The three key variables are low (the first index of the current search space), high (the last index) and mid (the middle index). The search space is the part of the list that could still contain the target.

三个关键变量是 low（当前搜索空间的起始下标）、high（结束下标）和 mid（中间下标）。搜索空间就是列表中仍可能包含目标值的那一部分。

Binary search is sometimes called 'half-interval search' or 'logarithmic search' because the search interval is halved and the running time grows logarithmically.

二分查找有时也被称为 '折半查找' 或 '对数查找'，因为搜索区间被不断减半，运行时间呈对数增长。

---

2. Core Idea: Divide and Conquer | 核心思想：分而治之

The algorithm follows a divide-and-conquer strategy. The problem of searching the whole list is reduced to searching a smaller sub-list. Each step divides the current search interval into two halves.

该算法采用分而治之的策略。搜索整个列表的问题被简化为搜索一个较小的子列表。每一步都将当前搜索区间分成两半。

Because the list is sorted, the algorithm can determine which half could contain the target by checking the middle value. If the target is greater than the middle value, the left half can be ignored; if it is smaller, the right half can be ignored.

由于列表是有序的，算法可以通过检查中间值来确定哪一半可能包含目标值。如果目标值大于中间值，则可以忽略左半部分；如果目标值小于中间值，则可以忽略右半部分。

This halving behaviour is why the number of comparisons grows much more slowly than the number of items. Doubling the size of the list adds only one extra comparison.

这种减半行为正是比较次数增长速度远慢于元素数量的原因。列表长度翻倍，只会增加一次比较。

Divide and conquer appears elsewhere in the specification, for example in merge sort and quick sort. Binary search is the simplest example of reducing a problem to a smaller instance of itself.

分而治之在考纲的其他地方也会出现，例如归并排序和快速排序。二分查找是把问题化简为自身更小规模实例的最简单例子。

---

3. Preconditions: Sorted Data | 前提条件：有序数据

Binary search only works correctly on sorted data. If the list is not sorted, the assumption that all values left of the middle are smaller and all values right are larger is false.

二分查找只有在数据有序时才能正确工作。如果列表未排序，那么 '中间值左边都更小、右边都更大' 的假设就不成立。

For Edexcel A-Level questions, you must state that the data has to be sorted before binary search can be used, and you should be able to explain what happens if it is not sorted: the algorithm may return the wrong index or incorrectly report that the target is absent.

在 Edexcel A-Level 考题中，你必须说明使用二分查找前数据必须已经排序，并且要能解释未排序时会发生什么：算法可能返回错误的下标，或者错误地报告目标值不存在。

The list may be sorted in ascending or descending order. If it is descending, the comparison logic must be reversed: when the target is smaller than the middle value, you search the left half instead of the right half.

列表可以按升序或降序排列。如果是降序，比较逻辑必须反过来：当目标值小于中间值时，应搜索左半部分而不是右半部分。

Sorting itself has a cost, usually O(n log n) for an efficient comparison sort. If you only need to search once, sorting first may be slower overall than a single linear search; binary search pays off when the data is already sorted or when many searches are performed.

排序本身是有代价的，高效的比较排序通常为 O(n log n)。如果只需要查找一次，先排序再二分查找可能整体上比一次线性查找更慢；当数据本身有序或需要执行多次查找时，二分查找才体现出优势。

---

4. Step-by-Step Algorithm | 算法步骤详解

Step 1: set low to 0 and high to the last index of the list, which is length − 1. These two values define the current search space.

第 1 步：将 low 设为 0，将 high 设为列表最后一个下标，即长度 − 1。这两个值定义了当前的搜索空间。

Step 2: while low is less than or equal to high, calculate the middle index. Integer division is used, so any fractional part is discarded.

第 2 步：当 low 小于或等于 high 时，计算中间下标。这里使用整数除法，因此小数部分被舍去。

广告 / Sponsored

mid = ⌊(low + high) ÷ 2⌋

Step 3: compare the value at mid with the target. If they are equal, return mid and stop. If the middle value is less than the target, the target must be in the right half, so set low to mid + 1. If the middle value is greater than the target, set high to mid − 1.

第 3 步：将 mid 处的值与目标值比较。如果相等，返回 mid 并停止。如果中间值小于目标值，目标值必定在右半部分，因此令 low 等于 mid + 1。如果中间值大于目标值，则令 high 等于 mid − 1。

Step 4: if the loop ends because low has become greater than high, the search space is empty and the target is not in the list. Return −1 or a suitable 'not found' message.

第 4 步：如果循环因为 low 大于 high 而结束，说明搜索空间已为空，目标值不在列表中。返回 −1 或相应的 '未找到' 信息。

The loop condition low ≤ high is essential. It guarantees that the algorithm checks the final remaining element before concluding that the target is absent.

循环条件 low ≤ high 至关重要。它保证算法在判定目标值不存在之前，会检查最后一个剩余元素。

---

5. Worked Example with Trace Table | 逐步追踪示例

Consider the sorted list [3, 7, 11, 19, 24, 31, 42, 56] and a target of 31. The indices run from 0 to 7.

考虑有序列表 [3, 7, 11, 19, 24, 31, 42, 56]，目标值为 31。下标从 0 到 7。

Step | 步骤	low	high	mid	list[mid]	Decision | 判定
1	0	7	3	19	19 < 31, so low = 4 | 19 < 31，令 low = 4
2	4	7	5	31	Match, return index 5 | 匹配，返回下标 5

Now consider a target of 25, which is not in the list. The trace shows how the search space shrinks until it becomes empty.

再考虑目标值 25，它不在列表中。追踪过程显示搜索空间如何不断缩小直至为空。

Step | 步骤	low	high	mid	list[mid]	Decision | 判定
1	0	7	3	19	19 < 25, low = 4 | 19 < 25，low = 4
2	4	7	5	31	31 > 25, high = 4 | 31 > 25，high = 4
3	4	4	4	24	24 < 25, low = 5 | 24 < 25，low = 5
4	5	4	—	—	low > high, stop and return −1 | low > high，停止并返回 −1

Exam answers should show every value of low, high and mid in a table like this, together with the comparison made at each stage.

考试答案应当用这样的表格列出每一轮的 low、high 和 mid 值，并写出每一阶段所做的比较。

---

6. Pseudocode and Python Implementation | 伪代码与 Python 实现

The following pseudocode follows the style commonly used in A-Level specifications. It uses ← for assignment and DIV for integer division.

下面的伪代码采用 A-Level 考纲常用的风格，使用 ← 表示赋值，使用 DIV 表示整数除法。

FUNCTION binarySearch(list, target)
    low ← 0
    high ← LENGTH(list) - 1
    WHILE low <= high DO
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

The Python version is almost identical, using // for integer division. Note that Python indices start at 0, so the last valid index is len(arr) - 1.

Python 版本几乎相同，只是用 // 表示整数除法。注意 Python 下标从 0 开始，因此最后一个有效下标是 len(arr) - 1。

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

Both implementations run in O(log n) time and use O(1) extra space, because only low, high and mid are stored.

这两种实现都以 O(log n) 时间运行，并且只使用 O(1) 额外空间，因为只需要存储 low、high 和 mid 三个变量。

---

7. Iterative vs Recursive | 迭代与递归

The version above is iterative: it uses a while loop and updates the same variables repeatedly. Iterative binary search has a constant space complexity of O(1).

上面的版本是迭代版本：它使用 while 循环并反复更新同一组变量。迭代版二分查找的空间复杂度为常数级 O(1)。

A recursive version calls itself on the left or right half until the target is found or the base case low > high is reached. Each recursive call adds a stack frame, so the space complexity becomes O(log n).

递归版本会在左半或右半部分上调用自身，直到找到目标值或达到基准情况 low > high。每次递归调用都会增加一个栈帧，因此空间复杂度变为 O(log n)。

FUNCTION binarySearchRec(list, target, low, high)
    IF low > high THEN
        RETURN -1
    ENDIF
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        RETURN mid
    ELSE IF list[mid] < target THEN
        RETURN binarySearchRec(list, target, mid + 1, high)
    ELSE
        RETURN binarySearchRec(list, target, low, mid - 1)
    ENDIF
ENDFUNCTION

In exams, either version is usually accepted. The iterative version is often preferred in mark schemes because it is easier to trace and does not risk a stack overflow on very large lists.

在考试中，两种版本通常都被接受。评分标准往往更偏好迭代版本，因为它更容易追踪，而且在超大列表上不会出现栈溢出。

---

8. Complexity: Why O(log n) | 复杂度：为什么是 O(log n)

Each comparison halves the search space. After one step at most n ÷ 2 elements remain, after two steps n ÷ 4, and after k steps n ÷ 2ᵏ elements remain.

每次比较都会将搜索空间减半。第一步之后最多剩余 n ÷ 2 个元素，第二步之后剩余 n ÷ 4 个，第 k 步之后剩余 n ÷ 2ᵏ 个元素。

The search ends when only one element, or zero elements, remain. Setting the remaining size to 1 gives the maximum number of halvings.

当只剩一个元素或零个元素时，搜索结束。将剩余规模设为 1，即可得到最大减半次数。

n ÷ 2ᵏ = 1 → 2ᵏ = n → k

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

备考资讯每日更新，关注不错过

考纲变化 · 科目分析 · 学习方法

在微信里长按二维码识别关注
或截图后用「扫一扫 → 相册」选择本图

公众号：tutorhao