第 46 章一分为二——二分查找

🏗️ 前情回顾：前两章你深入了递归的世界——回溯枚举、记忆化优化。但从本章开始，我们要学几个不依赖递归却同样强大的算法思想。第一个是二分——每次把问题砍掉一半。听起来像分治？不完全是。二分查找的精髓在于：利用"有序性"来排除不可能的区域。

🎯 本章目标

学完这一章，你能：

理解二分查找的核心思想——"猜数字"策略
写出标准的二分查找代码（while 循环版）
掌握 lower_bound 和 upper_bound 的概念与区别
使用 STL 的 binary_search、lower_bound、upper_bound
正确处理二分的边界（左闭右闭 vs 左闭右开）
避免二分最常见的 3 个 bug

📖 故事引入

你来玩一个游戏：我心里想了一个 1~1000 之间的整数，你每次猜一个数，我告诉你"大了"还是"小了"或者"猜中了"。你要用最少的次数猜中它。

你打算怎么猜？从 1 开始一个个往上猜？那最多要猜 1000 次。太傻了。

聪明的方法是：第一次猜 500。如果我说"大了"，你就知道正确答案在 1~499 之间；如果我说"小了"，正确答案就在 501~1000 之间。不管哪种情况，你都一刀砍掉了一半的可能性。

然后你在剩下的一半里继续猜。每次砍一半：500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1。最多 10 次！

1000 个数，10 次就能定位。2^10 = 1024 > 1000。这就是二分查找的威力——复杂度 O(log n)。

你再想想查字典：你要找一个单词，你是从第一页开始翻，还是直接翻到大概的字母区间？后者就是二分查找在生活中的自然运用。

🧱 知识讲解

46.1 二分查找的前提

二分查找有一个硬性前提：数据必须有序（升序或降序）。

为什么？因为二分依赖于"根据中间值判断目标在哪一边"。如果数据是乱的，"中间值比目标大"不能说明任何问题——目标可能在任何地方。

46.2 标准二分查找（左闭右闭）

问题：在升序数组 a[0..n-1] 中查找值 x，找到返回下标，找不到返回 -1。

cpp

int binarySearch(int a[], int n, int x) {
    int l = 0, r = n - 1;          // 搜索区间 [l, r]，左闭右闭
    while (l <= r) {               // 区间非空时继续
        int mid = l + (r - l) / 2; // 防溢出写法，等价于 (l+r)/2
        if (a[mid] == x)
            return mid;            // 找到了！
        else if (a[mid] < x)
            l = mid + 1;           // x 在右半部分
        else
            r = mid - 1;           // x 在左半部分
    }
    return -1;                     // 没找到
}

⚠️ mid = l + (r - l) / 2 而不是 (l + r) / 2——后者在 l 和 r 都很大时可能溢出（l+r > 2^31-1）。

跟踪一下：数组 {2, 5, 8, 12, 16}，查找 x = 8：

第1轮：l=0, r=4, mid=2, a[2]=8 → 找到了！

查找 x = 10：

第1轮：l=0, r=4, mid=2, a[2]=8 < 10 → l=3
第2轮：l=3, r=4, mid=3, a[3]=12 > 10 → r=2
l=3 > r=2 → 退出，返回 -1

46.3 左闭右闭 vs 左闭右开

二分有两大流派：

	左闭右闭 `[l, r]`	左闭右开 `[l, r)`
初始化	`l=0, r=n-1`	`l=0, r=n`
循环条件	`while (l <= r)`	`while (l < r)`
l 更新	`l = mid + 1`	`l = mid + 1`
r 更新	`r = mid - 1`	`r = mid`

左闭右开的写法：

cpp

int binarySearch(int a[], int n, int x) {
    int l = 0, r = n;              // [l, r)，r 是开区间，初始为 n
    while (l < r) {                // 区间非空
        int mid = l + (r - l) / 2;
        if (a[mid] == x)
            return mid;
        else if (a[mid] < x)
            l = mid + 1;
        else
            r = mid;               // 右开，所以 r = mid（不包含 mid）
    }
    return -1;
}

初学者建议固定用一种，推荐左闭右闭（更直观）。STL 内部用的是左闭右开。

46.4 lower_bound 与 upper_bound

这两个概念是二分查找的进阶用法：

lower_bound：第一个 大于等于 x 的位置
upper_bound：第一个大于 x 的位置

例如数组 {1, 2, 2, 2, 3, 5}：

lower_bound(2) → 下标 1（第一个 2）
upper_bound(2) → 下标 4（第一个大于 2 的，即 3）
元素 2 的出现次数 = upper_bound(2) - lower_bound(2) = 3

实现 lower_bound（左闭右闭）：

cpp

int lowerBound(int a[], int n, int x) {
    int l = 0, r = n - 1, ans = n;  // ans 初始为 n（表示找不到）
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) {
            ans = mid;               // 记录当前位置
            r = mid - 1;             // 往左找更小的
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

46.5 STL 中的二分函数

C++ 标准库已经帮你写好了，都在 <algorithm> 里：

cpp

#include <algorithm>
#include <vector>
using namespace std;

vector<int> a = {1, 2, 2, 2, 3, 5};

bool found = binary_search(a.begin(), a.end(), 3);   // true
bool found2 = binary_search(a.begin(), a.end(), 4);  // false

auto it1 = lower_bound(a.begin(), a.end(), 2);  // 指向第一个 2
auto it2 = upper_bound(a.begin(), a.end(), 2);  // 指向 3

int cnt = it2 - it1;   // 2 的出现次数 = 3
int idx = it1 - a.begin();  // 下标 = 1

这些函数都要求序列有序，返回的是迭代器。

✋ 动手试试

试试 1：自己写一个二分查找，在 {3, 7, 9, 15, 21, 33, 40} 中查找 21。用纸笔跟踪 l、r、mid 的变化。

试试 2：写 lower_bound 函数，在 {1, 3, 3, 3, 5, 7} 中分别查 3、4、8，输出下标。查 8 应该返回 6（数组长度，表示所有元素都小于 8）。

试试 3：用 STL 的 binary_search 和 lower_bound 测试上面的例子，对照结果是否一致。

⚠️ 容易犯的错

错 1：循环条件写错

❌ 左闭右闭用 while (l < r) → 区间只有一个元素时直接跳过

✅ 左闭右闭用 while (l <= r)

错 2：mid 溢出

❌ int mid = (l + r) / 2; → l 和 r 都接近 2^31-1 时溢出

✅ int mid = l + (r - l) / 2;

错 3：l 和 r 更新写错

❌ l = mid; 或 r = mid;（左闭右闭时）→ 可能死循环

✅ l = mid + 1; 和 r = mid - 1;（确保区间每次至少缩小 1）

错 4：忘了要求数组有序

❌ 在乱序数组上跑二分 → 结果不可预测

✅ 二分前先排序，或确认数据本身有序

错 5：lower_bound 实现时 ans 没初始化

❌ 如果所有元素都小于 x，lower_bound 应返回 n

✅ int ans = n; 作为默认值

📝 练习

基础题

1. 选择题

（1）在 1024 个有序元素中二分查找，最多比较多少次？
A. 10 B. 11 C. 512 D. 1024

（2）在数组 {2, 4, 4, 4, 7, 9} 中，upper_bound(4) 返回的下标是？
A. 1 B. 3 C. 4 D. 5

（3）二分查找的前提是？
A. 数组元素不重复 B. 数组有序 C. 元素是整数 D. 数组长度是 2 的幂

2. 填空题

（1）二分查找每次把搜索范围____，时间复杂度是____。

（2）lower_bound(x) 返回第一个____的位置，upper_bound(x) 返回第一个____的位置。

（3）防溢出的 mid 写法：mid = ____ + (____ - ____) / 2。

提高题

3. 编程题 — 查找首次出现位置

在升序数组中可能包含重复元素。写函数 int firstOccur(int a[], int n, int x)，返回 x 第一次出现的下标，若不存在返回 -1。不要用 STL。

4. 编程题 — 统计出现次数

利用 lower_bound 和 upper_bound（手写或用 STL），写函数统计给定值在有序数组中出现的次数。

挑战题

5. 编程题 — 搜索旋转排序数组

一个原本升序的数组在某个位置被"旋转"了，例如 {4, 5, 6, 7, 0, 1, 2}。在这个数组中查找目标值，返回下标，找不到返回 -1。要求 O(log n) 复杂度。

提示：虽然数组不是全局有序，但每次二分后，左半部分或右半部分必有一段是有序的。判断目标是否在有序那段里，然后缩小范围。

🧠 本章小结

二分查找 = 每次砍一半

前提：数据有序

标准框架（左闭右闭）：
  l=0, r=n-1
  while (l <= r):
    mid = l + (r-l)/2
    if a[mid]==x → 找到了
    if a[mid]<x  → l=mid+1
    if a[mid]>x  → r=mid-1

防溢出：mid = l + (r-l)/2（而不是 (l+r)/2）

lower_bound(第一个≥x) / upper_bound(第一个>x)

STL：binary_search, lower_bound, upper_bound

边界 bug 三件套：
  ① 循环条件写错
  ② mid 溢出（用防溢出写法）
  ③ l/r 更新写错导致死循环

📝 配套练习

共7题。二分从精确查找→上下界→最接近→答案过渡，为Ch47二分答案铺路。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P2249	https://hydro.ac/p/luogu-P2249	lower_bound、第一个≥x
◆ 拓展	luogu-P1102	https://hydro.ac/p/luogu-P1102	lower_bound+upper_bound、出现次数
◆ 拓展	luogu-P1678	https://hydro.ac/p/luogu-P1678	二分找最接近值
◆ 拓展	luogu-P1873	https://hydro.ac/p/luogu-P1873	二分答案过渡（砍树）
◆ 拓展	luogu-P1918	https://hydro.ac/p/luogu-P1918	二分查找、保龄球
◆ 拓展	luogu-P5747	https://hydro.ac/p/luogu-P5747	二分、有序插入
◆ 拓展	luogu-P5748	https://hydro.ac/p/luogu-P5748	二分、查找区间

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。二分从精确查找→上下界→最接近→答案过渡，为Ch47二分答案铺路。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P2249	https://hydro.ac/p/luogu-P2249	lower_bound、第一个≥x
◆ 拓展	luogu-P1102	https://hydro.ac/p/luogu-P1102	lower_bound+upper_bound、出现次数
◆ 拓展	luogu-P1678	https://hydro.ac/p/luogu-P1678	二分找最接近值
◆ 拓展	luogu-P1873	https://hydro.ac/p/luogu-P1873	二分答案过渡（砍树）
◆ 拓展	luogu-P1918	https://hydro.ac/p/luogu-P1918	二分查找、保龄球
◆ 拓展	luogu-P5747	https://hydro.ac/p/luogu-P5747	二分、有序插入
◆ 拓展	luogu-P5748	https://hydro.ac/p/luogu-P5748	二分、查找区间

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能写出标准二分查找代码（while 循环版）
[ ] 我理解 lower_bound 和 upper_bound 的区别
[ ] 我能使用 STL 的二分函数
[ ] 我知道 mid = l + (r-l)/2 是为什么
[ ] 我理解左闭右闭和左闭右开的差异
[ ] 我能避免二分最常见的三个 bug

🚀 下章预告：二分不光能查找具体的值，还能查找"满足条件的最小值"——这就是二分答案！当你看到"最大值最小"或"最小值最大"这种表述时，二分答案就是你最锋利的武器。第 47 章，我们把手伸向更广阔的领域！🎯

第 46 章 一分为二——二分查找 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

46.1 二分查找的前提 ​

46.2 标准二分查找（左闭右闭） ​

46.3 左闭右闭 vs 左闭右开 ​

46.4 lower_bound 与 upper_bound ​

46.5 STL 中的二分函数 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：循环条件写错 ​

错 2：mid 溢出 ​

错 3：l 和 r 更新写错 ​

错 4：忘了要求数组有序 ​

错 5：lower_bound 实现时 ans 没初始化 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​