3.9 二分查找与边界变体

这一节，你能解决什么问题

学完这一节，你能够：

1. 正确实现二分查找，避免边界 bug（如溢出）
2. 理解二分查找的边界变体（lower_bound、upper_bound），知道为什么边界条件不同
3. 手动追踪变体执行过程，理解每一步的边界变化
4. 推导复杂度和正确性，不是死记结论

---

问题情境

2006年，Joshua Bloch 发现 Java 的 Arrays.binarySearch 有隐藏 bug：

int mid = (low + high) / 2;  // low + high 溢出！

修复：

int mid = low + (high - low) // 2;  // 避免溢出

教训：二分查找看起来简单，但边界容易出错。

更难的是边界变体：

数组：[1, 2, 2, 2, 3]

问题 1：找第一个 ≥ 2 的位置 → 答案是 1
问题 2：找第一个 > 2 的位置 → 答案是 4
问题 3：找最后一个 ≤ 2 的位置 → 答案是 3

这些问题在算法竞赛和实际开发中非常常见，比如：

• 插入排序找插入位置
• 统计有序数组中某值出现的次数
• 范围查询

核心挑战：边界条件稍有不同，循环条件和区间含义就完全不同。

---

直观思路

二分查找：每次排除一半，快速缩小范围。

基本思路

有序数组中找元素：

1. 看中间元素
2. 如果比目标大，排除右边一半
3. 如果比目标小，排除左边一半
4. 重复

关键：每次排除一半 → log n 次 → O(log n)。

变体思路：找第一个 ≥ x 的位置

问题：数组 [1, 2, 2, 2, 3]，找第一个 ≥ 2 的位置。

直观想法：找到 2 后，继续往左找，直到没有 2 为止。

问题：这样是 O(n)，因为可能有 n/2 个 2。

二分思路：

• 如果 A[mid] < 2，答案在右边
• 如果 A[mid] ≥ 2，答案可能是 mid，也可能在左边

关键洞察：当 A[mid] ≥ x 时，我们不确定 mid 是不是第一个，所以要保留 mid 在搜索范围内。

这引出了一个重要的边界问题：搜索区间是 [low, high] 还是 [low, high)？

---

这个方法是怎么想到的

基本二分查找的思路

问题：有序数组中找元素。

朴素方法：逐个检查 → O(n)

洞察：有序 → 比中间元素 → 排除一半

关键：每次缩小一半 → log n 次

边界设计：

• 搜索范围：[low, high]，闭区间
• 终止条件：low > high（搜索范围空）
• mid 更新：
  • A[mid] < x：排除 [low, mid]，答案在 [mid+1, high]
  • A[mid] > x：排除 [mid, high]，答案在 [low, mid-1]

变体的思路：为什么要改变边界？

问题：找第一个 ≥ x 的位置。

核心困难：找到 x 后，不知道这是第一个还是后面的 x。

关键洞察：

当 A[mid] ≥ x 时：

• mid 可能是答案
• 答案也可能在 mid 左边

所以 不能排除 mid！

这导致：

• 搜索范围必须是 [low, high)，半开区间
• 因为 mid 不能排除，high 要能等于 mid
• 终止条件是 low == high（区间只剩一个候选）

为什么用 [low, high) 而不是 [low, high]？

区间类型	搜索范围	终止条件	适用场景
[low, high]	闭区间	low > high	找精确值
[low, high)	半开区间	low == high	找边界位置

直觉：半开区间在编程中更常见，因为：

• [low, high) 包含 high - low 个元素（容易计算）
• 边界变体中，答案可能是 len(A)（所有元素都 < x）
• 用 high = len(A) 很自然

---

规范定义

基本二分查找

输入：有序数组 A，目标 x 输出：x 的位置（或 -1 如果不存在）

边界变体

变体	含义	等价定义
lower_bound(x)	第一个 ≥ x 的位置	min{i : A[i] ≥ x}
upper_bound(x)	第一个 > x 的位置	min{i : A[i] > x}

关键关系：

• x 在 A 中的出现次数 = upper_bound(x) - lower_bound(x)
• 如果 lower_bound(x) < len(A) 且 A[lower_bound(x)] == x，则 x 存在

---

算法实现

基本二分查找

def binary_search(A, x):
    low = 0
    high = len(A) - 1
    while low <= high:              # 闭区间 [low, high]
        mid = low + (high - low) // 2  # 避免溢出
        if A[mid] == x:
            return mid
        elif A[mid] < x:
            low = mid + 1            # 排除 [low, mid]
        else:
            high = mid - 1           # 排除 [mid, high]
    return -1

一步步执行：

数组：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
查找：11

Step 1: low=0, high=9, mid=5, A[5]=11 → 找到！

查找：8

Step 1: low=0, high=9, mid=5, A[5]=11 > 8 → high=4
Step 2: low=0, high=4, mid=2, A[2]=5 < 8 → low=3
Step 3: low=3, high=4, mid=3, A[3]=7 < 8 → low=4
Step 4: low=4, high=4, mid=4, A[4]=9 > 8 → high=3
Step 5: low=4 > high=3 → 未找到

变体：lower_bound（第一个 ≥ x 的位置）

def lower_bound(A, x):
    low = 0
    high = len(A)              # 注意：不是 len(A) - 1
    while low < high:          # 注意：不是 low <= high
        mid = low + (high - low) // 2
        if A[mid] >= x:
            high = mid          # 保留 mid，答案可能是 mid
        else:
            low = mid + 1       # 排除 mid，答案在右边
    return low                   # low == high

为什么 high = len(A) 而不是 len(A) - 1？

因为答案可能是 len(A)！

例如：A = [1, 2, 3]，x = 5，第一个 ≥ 5 的位置是 3（即 len(A)，表示"不存在"）。

如果用 high = len(A) - 1 = 2，则无法返回 3。

为什么 low < high 而不是 low <= high？

因为区间是 [low, high)，当 low == high 时区间为空（包含 0 个元素），这是唯一合理的终止条件。

如果用 low <= high，则区间 [low, high] 当 low == high 时包含 1 个元素，但我们不知道应该用闭区间还是半开区间。

手动追踪例子：A = [1, 2, 2, 2, 3]，找 lower_bound(2)

初始：low=0, high=5

Step 1: mid=2, A[2]=2 ≥ 2 → high=2, 区间变为 [0, 2)
        数组状态：[1, 2 | 2, 2, 3]
        搜索范围：A[0..1]（2 个元素）

Step 2: mid=1, A[1]=2 ≥ 2 → high=1, 区间变为 [0, 1)
        数组状态：[1 | 2, 2, 2, 3]
        搜索范围：A[0]（1 个元素）

Step 3: mid=0, A[0]=1 < 2 → low=1, 区间变为 [1, 1)
        数组状态：[1 | 2, 2, 2, 3]
        搜索范围：空（终止）

结果：low=1，即第一个 ≥ 2 的位置
验证：A[1]=2 ✓

变体：upper_bound（第一个 > x 的位置）

def upper_bound(A, x):
    low = 0
    high = len(A)
    while low < high:
        mid = low + (high - low) // 2
        if A[mid] > x:
            high = mid
        else:
            low = mid + 1
    return low

手动追踪例子：A = [1, 2, 2, 2, 3]，找 upper_bound(2)

初始：low=0, high=5

Step 1: mid=2, A[2]=2 不 > 2 → low=3, 区间变为 [3, 5)
        数组状态：[1, 2, 2 | 2, 3]
        搜索范围：A[3..4]（2 个元素）

Step 2: mid=4, A[4]=3 > 2 → high=4, 区间变为 [3, 4)
        数组状态：[1, 2, 2, 2 | 3]
        搜索范围：A[3]（1 个元素）

Step 3: mid=3, A[3]=2 不 > 2 → low=4, 区间变为 [4, 4)
        数组状态：[1, 2, 2, 2 | 3]
        搜索范围：空（终止）

结果：low=4，即第一个 > 2 的位置
验证：A[4]=3 > 2 ✓，且 A[3]=2 ≤ 2 ✓

计算 2 出现的次数：

• lower_bound(2) = 1
• upper_bound(2) = 4
• 次数 = 4 - 1 = 3 ✓

---

正确性分析

基本二分查找：循环不变式

不变式：每次循环开始时：

• 目标 x 如果存在，一定在 [low, high] 范围内
• [low, high] 外的元素都不是 x

证明：

1. 初始化

循环开始前：low = 0, high = len(A) - 1。

• [low, high] 是整个数组
• [low, high] 外的元素：空集

所以：x 如果存在，一定在 [low, high] 内；外部没有元素。

初始化成立。

2. 保持

假设循环开始时不变式成立。考虑三种情况：

情况 A[mid] < x：

• 因为 A 有序，A[low..mid] 所有元素都 ≤ A[mid] < x
• 所以 x 不可能在 [low, mid] 内
• 更新 low = mid + 1 后，新的 [low, high] 排除了不可能的区域
• 推导过程：A[mid] < x ⇒ ∀i ∈ [low, mid], A[i] ≤ A[mid] < x ⇒ x ∉ [low, mid]
• 新搜索范围 [mid+1, high] 仍可能包含 x

情况 A[mid] > x：

• 因为 A 有序，A[mid..high] 所有元素都 ≥ A[mid] > x
• 所以 x 不可能在 [mid, high] 内
• 更新 high = mid - 1 后，新的 [low, high] 排除了不可能的区域
• 推导过程：A[mid] > x ⇒ ∀i ∈ [mid, high], A[i] ≥ A[mid] > x ⇒ x ∉ [mid, high]
• 新搜索范围 [low, mid-1] 仍可能包含 x

情况 A[mid] == x：

• 直接返回 mid，不变式仍然成立（返回前已找到）

保持成立。

3. 终止

循环终止条件：low > high。

此时 [low, high] 是空集，搜索范围空。

由不变式：x 如果存在，一定在 [low, high] 内。

但 [low, high] 为空，所以 x 不存在。

返回 -1 正确。

证毕。

lower_bound：循环不变式

不变式：每次循环开始时：

• 答案（第一个 ≥ x 的位置）在 [low, high] 内
• A[0..low-1] 都 < x（low 之前都不是答案）
• A[high..n-1] 都 ≥ x（high 及之后可能包含答案，但 high 本身可能是答案）

证明：

1. 初始化

循环开始前：low = 0, high = len(A)。

• 答案范围 [0, len(A)]：正确（答案可能是 len(A)）
• A[0..low-1] = A[∅]：空集，成立
• A[high..n-1]：如果 high = n，空集，成立

初始化成立。

2. 保持

情况 A[mid] ≥ x：

• mid 可能是答案（因为 A[mid] ≥ x）
• 答案也可能在 mid 之前（如果有更早的 ≥ x）
• 更新 high = mid，保留 mid 在搜索范围内
• 新的 [low, high] 仍包含答案

情况 A[mid] < x：

• A[mid] < x，所以 mid 不可能是答案
• 答案一定在 mid 之后
• 更新 low = mid + 1
• 新的 [low, high] 仍包含答案

保持成立。

3. 终止

循环终止条件：low == high。

• 答案在 [low, high] 内
• 但 [low, high] 只有一个位置（low == high）
• 所以答案就是 low

返回 low 正确。

证毕。

---

复杂度分析

基本二分查找

每次循环，搜索范围缩小一半。

推导：

设数组大小为 n。

第 1 次循环后，范围 ≤ n/2 第 2 次循环后，范围 ≤ n/4 ... 第 k 次循环后，范围 ≤ n/2^k

循环终止条件：范围 < 1（即范围空）

n / 2^k < 1
n < 2^k
k > log₂(n)

所以最大循环次数 k = ⌊log₂(n)⌋ + 1 = O(log n)。

时间复杂度：O(log n)

空间复杂度：O(1)（迭代实现）

变体

lower_bound 和 upper_bound 的循环次数分析与基本二分查找相同。

每次循环：

• 比较 1 次
• 更新边界 1 次

总比较次数 = O(log n)

---

什么时候不该用这个方法

该用二分查找的情况

• 数组有序
• 静态数据（不频繁插入删除）

不该用二分查找的情况

• 数组无序（先排序 Θ(n log n)，可能不如直接线性查找）
• 频繁插入删除（用哈希表或平衡树）

边界变体的使用场景

问题	用哪个变体
找第一个 ≥ x 的位置	lower_bound
找第一个 > x 的位置	upper_bound
找最后一个 ≤ x 的位置	upper_bound(x) - 1
找最后一个 < x 的位置	lower_bound(x) - 1
统计 x 出现次数	upper_bound(x) - lower_bound(x)

---

本节小结

解决了什么问题？

有序数组快速查找，O(log n)。边界变体处理"找第一个"类问题。

核心方法是什么？

每次排除一半 → log n 次。边界变体使用半开区间 [low, high)。

为什么正确？

循环不变式保证目标始终在范围内。变体的不变式保证答案不会丢失。

代价是什么？

需要有序数组。如果频繁插入删除，维护有序的成本高。

适用场景？

静态有序数据查找。边界变体用于插入位置、范围查询、统计次数。

---

练习

基本理解

练习 1：实现二分查找，特别注意边界条件。

练习 2：数组 [1, 2, 2, 2, 3, 4]，手动追踪：

• lower_bound(2)：每步记录 low、high、mid
• upper_bound(2)：每步记录 low、high、mid

练习 3：用二分查找计算 sqrt(1000) 的整数部分（找最大的 x 满足 x² ≤ 1000）。

错误诊断

练习 4：以下实现有什么问题？

def binary_bug(A, x):
    low, high = 0, len(A) - 1
    while low < high:           # ← 问题 1
        mid = (low + high) // 2  # ← 问题 2
        if A[mid] == x:
            return mid
        elif A[mid] < x:
            low = mid           # ← 问题 3
        else:
            high = mid          # ← 问题 4
    return -1

分析：循环条件、溢出、范围更新是否正确？找出 4 个问题并修复。

变体应用

练习 5：实现 lower_bound 和 upper_bound 后，回答：

A = [1, 3, 3, 3, 5, 7, 9]

• lower_bound(3) = ?
• upper_bound(3) = ?
• 3 出现几次？
• lower_bound(4) = ? 含义？
• upper_bound(0) = ? 含义？

设计练习

练习 6：旋转有序数组的二分查找。

数组在某个点旋转，如 [4, 5, 6, 7, 0, 1, 2]。

设计 O(log n) 算法找目标值。

提示：先判断 mid 在左半还是右半，再判断 target 在哪半。

---

上一节：3.8 字符串匹配

下一节：3.10 综合练习