第5章二分算法

🎯 本章学习目标

通过本章的学习，你将能够：

理解二分思想：掌握二分查找的核心原理——利用单调性每次砍半
熟练二分查找：能手写左闭右闭和左闭右开两种写法
区分两种区间：清楚左闭右闭和左闭右开的区别，不会搞混边界
掌握 lower/upper_bound：理解第一个 ≥ 和第一个 > 的含义，会手写
精通二分答案：掌握"二分枚举答案 + check验证"的经典模式
设计 check 函数：能根据题目设计正确的可行性验证函数
识别二分题型：看到"最大值最小化/最小值最大化"就想到二分答案
理解整数二分：掌握整数二分的取整方向，避免死循环
了解浮点二分：知道浮点数二分的写法和终止条件
分析时间复杂度：能快速计算二分算法的时间复杂度

🗺️ 本章知识图谱

二分算法
├── 二分查找
│   ├── 前提：序列必须有序
│   ├── 核心思想：每次比较中间，砍掉一半
│   ├── 左闭右闭 [left, right]
│   │   ├── 初始：left=0, right=n-1
│   │   ├── 循环：while(left <= right)
│   │   └── 更新：left=mid+1 / right=mid-1
│   ├── 左闭右开 [left, right)
│   │   ├── 初始：left=0, right=n
│   │   ├── 循环：while(left < right)
│   │   └── 更新：left=mid+1 / right=mid
│   ├── mid 计算：left + (right-left)/2（防溢出）
│   ├── lower_bound（第一个 ≥ target）
│   └── upper_bound（第一个 > target）
├── 二分答案
│   ├── 适用条件：答案具有单调性
│   ├── 核心模式：二分枚举答案 + check验证
│   ├── 经典题型
│   │   ├── 最大值最小化
│   │   ├── 最小值最大化
│   │   └── 求第 k 大/小
│   └── check 函数设计
│       ├── 判断答案是否可行
│       └── 复杂度要能接受
├── 整数二分
│   ├── 取整方向：向下取整 / 向上取整
│   ├── 死循环陷阱（left=mid 时要向上取整）
│   └── 边界处理
└── 浮点数二分
    ├── 直接 = mid，不用 ±1
    ├── 终止条件：right - left < eps
    └── 或固定迭代次数（100次足够）

📖 引言

二分利用"单调性"将搜索空间每次砍半，把 O(n) 的查找压缩到 O(log n)；更进阶的"二分答案"更是解决"最大值最小化/最小值最大化"问题的利器。

一、二分查找

🔍 核心思想

在有序序列中，每次取中间元素与目标比较，砍掉一半搜索空间。

二分查找（Binary Search）的前提是序列有序。每次比较中间元素 a[mid] 与目标值 target：

a[mid] == target → 找到了 ✅
a[mid] < target → 目标只可能在右半部分，令 left = mid + 1
a[mid] > target → 目标只可能在左半部分，令 right = mid - 1

每轮排除一半元素，时间复杂度 O(log n)。

📐 算法流程（左闭右闭写法）

left = 0, right = n - 1
while (left <= right):
    mid = left + (right - left) / 2
    if a[mid] == target: return mid
    else if a[mid] < target: left = mid + 1
    else: right = mid - 1
return -1  // 未找到

🧩 代码模板：左闭右闭 [left, right]

cpp

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

// 在有序数组 a 中查找 target，返回下标；未找到返回 -1
int binarySearch(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size() - 1;  // 闭区间 [left, right]
    while (left <= right) {                    // left == right 时区间仍有效
        int mid = left + (right - left) / 2;   // 等价于 (left+right)/2，防溢出
        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1;   // 目标在右半
        else right = mid - 1;                        // 目标在左半
    }
    return -1;  // 区间为空，未找到
}

int main() {
    vector<int> a = {1, 3, 5, 7, 9, 11, 13};
    cout << binarySearch(a, 7) << endl;   // 输出 3
    cout << binarySearch(a, 4) << endl;   // 输出 -1
    return 0;
}

🧩 代码模板：左闭右开 [left, right)

cpp

// 左闭右开写法：区间 [left, right)，right 指向"末尾元素的下一个位置"
int binarySearch(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size();  // 注意 right = n，不是 n-1
    while (left < right) {                 // left == right 时空区间，退出
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1;
        else right = mid;                  // 注意：mid 不在区间内，故 right = mid（不是 mid-1）
    }
    return -1;
}

⚠️ 两种写法对比（高频考点！）

对比项	左闭右闭 `[left, right]`	左闭右开 `[left, right)`
初始 right	`n - 1`	`n`
循环条件	`left <= right`	`left < right`
缩到左半	`right = mid - 1`	`right = mid`
缩到右半	`left = mid + 1`	`left = mid + 1`
mid 计算	`left + (right-left)/2`	`left + (right-left)/2`

🔑 记忆口诀：闭区间用 <= 和 -1，开区间用 < 和不减。两种写法选一种练熟即可，不要混用！

🚫 死循环是怎么来的？

当区间只剩两个元素，且 mid 计算后更新 left = mid 或 right = mid 时，可能无法缩小区间：

left = 3, right = 4
mid = 3 + (4-3)/2 = 3
若 left = mid → left 仍为 3，区间永远不变 → 死循环！💥

避免方法：

左闭右闭写法中，更新时统一用 left = mid + 1 / right = mid - 1（不用 = mid）
若必须用 left = mid（如找下界），则 mid 要向上取整：mid = left + (right - left + 1) / 2

lower_bound 与 upper_bound

这是二分查找最常考的变体——在有重复元素的有序数组中找边界：

函数	含义	返回
lower_bound	第一个 ≥ target 的元素位置	下界
upper_bound	第一个 > target 的元素位置	上界
两者之间	所有 == target 的元素范围	`[lower, upper)`

数组: [1, 3, 3, 3, 5, 7], target = 3
lower_bound → 下标 1（第一个 ≥ 3）
upper_bound → 下标 4（第一个 > 3）
等值区间 = [1, 4)，即下标 1,2,3 共 3 个 3

STL 用法（C++ 标准库）

cpp

#include <iostream>
#include <vector>
#include <algorithm>  // lower_bound / upper_bound
using namespace std;

int main() {
    vector<int> a = {1, 3, 3, 3, 5, 7};
    int target = 3;

    // lower_bound 返回迭代器，减去 begin() 得到下标
    int lo = lower_bound(a.begin(), a.end(), target) - a.begin();
    int hi = upper_bound(a.begin(), a.end(), target) - a.begin();

    cout << "lower_bound = " << lo << endl;  // 1
    cout << "upper_bound = " << hi << endl;  // 4
    cout << "出现次数 = " << hi - lo << endl; // 3
    return 0;
}

手写 lower_bound / upper_bound 模板

cpp

// lower_bound: 找第一个 >= target 的位置
int lowerBound(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size();  // 左闭右开 [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] >= target) right = mid;   // 中点已满足，尝试找更左的
        else left = mid + 1;                  // 中点太小，往右
    }
    return left;  // left == right，即第一个 >= target 的位置
}

// upper_bound: 找第一个 > target 的位置
int upperBound(const vector<int>& a, int target) {
    int left = 0, right = (int)a.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] > target) right = mid;    // 中点已满足，尝试找更左的
        else left = mid + 1;                  // 中点 <= target，往右
    }
    return left;
}

⚠️ 易错点：lower_bound 的判断条件是 a[mid] >= target（不是 ==），upper_bound 是 a[mid] > target。两者只差一个等号！

二、二分答案（二分枚举法）

🔍 核心思想

当答案具有单调性时，可以二分枚举答案，用 check 函数判断"答案是否可行"。

二分答案不直接搜索数据，而是二分猜测答案的值，再验证这个值是否满足条件。它适用于：

题型	含义
最大值最小化	在所有合法方案中，让"最大代价"尽可能小
最小值最大化	在所有合法方案中，让"最小收益"尽可能大

单调性是前提：如果答案 x 可行，那么所有 ≥ x（或 ≤ x）的值也可行——这样才能二分。

📐 通用模板

// 左闭右开区间 [left, right)
left = 答案下界, right = 答案上界 + 1
while (left < right):
    mid = left + (right - left) / 2;  // 向下取整
    if (check(mid)):
        right = mid;   // 保留mid
    else:
        left = mid + 1; // 排除mid
return left;  // left是第一个满足条件的位置

🧩 经典例题：木材加工

题目：有 n 根木材，长度分别为 a[i]。要截出 k 段等长的木材，求每段的最大长度（整数）。

单调性分析：如果每段长度为 L 时能截出 ≥ k 段，那么长度 < L 时也一定能（甚至更多）→ 单调。

cpp

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

int n, k;
vector<int> a;

// check: 每段长度为 len 时，能否截出至少 k 段？
bool check(int len) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += a[i] / len;   // 第 i 根木材能截出 a[i]/len 段
        if (cnt >= k) return true;  // 提前满足，剪枝
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        maxLen = max(maxLen, a[i]);
    }

    // 二分答案：最大可行长度（最大值最小化的镜像——求最大值）
    int left = 1, right = maxLen;  // 长度至少为 1
    while (left < right) {
        int mid = left + (right - left + 1) / 2;  // ⚠️ 向上取整！
        if (check(mid)) {
            left = mid;         // mid 可行，尝试更大
        } else {
            right = mid - 1;    // mid 不可行，往小
        }
    }
    cout << left << endl;
    return 0;
}

⚠️ 取整方向至关重要：
当 left = mid（尝试保留更大值）时，mid 必须向上取整：(left + right + 1) / 2，否则两个元素时死循环！
当 right = mid（尝试保留更小值）时，mid 用向下取整：(left + right) / 2。

🧩 check 函数设计要点

要点	说明
返回 bool	`true` 表示该答案可行，`false` 表示不可行
O(n) 或 O(n log n)	check 本身要足够快，否则总复杂度会超时
利用单调性	确保可行/不可行状态在答案轴上单调
注意边界	答案下界和上界要取准，避免遗漏或越界

📌 常见二分答案题型

题型	check 函数思路
切木头/分段最大长度	统计能截出的段数 ≥ k
跳石头/移除元素最小距离	统计需要移除的数量 ≤ m
分配问题（最大和最小）	贪心检查每组之和是否 ≤ mid
求最小时间完成任务	检查给定时间内能否完成

三、整数二分 vs 浮点数二分

对比项	整数二分	浮点数二分
循环条件	`left < right` 或 `left <= right`	`right - left > eps`（精度控制）
mid 取整	需要考虑向上/向下取整	无需取整，直接 `(left+right)/2`
死循环风险	有（取整方向错误时）	无（实数连续）
更新方式	`left = mid+1` / `right = mid` 等	`left = mid` / `right = mid`
终止	区间为空或长度为 1	区间长度小于精度 eps

🧩 浮点数二分模板（求平方根）

cpp

#include <iostream>
#include <iomanip>
using namespace std;

// 求 sqrt(n)，精度 1e-7
double sqrtBinary(double n) {
    double left = 0, right = n;
    if (n < 1) right = 1;  // n < 1 时，平方根在 [0,1] 之间

    for (int i = 0; i < 100; i++) {  // 直接迭代 100 次，精度足够
        double mid = (left + right) / 2;
        if (mid * mid < n) left = mid;
        else right = mid;
    }
    return left;
}

int main() {
    double n;
    cin >> n;
    cout << fixed << setprecision(7) << sqrtBinary(n) << endl;
    return 0;
}

💡 推荐写法：浮点数二分直接固定迭代 100 次（每次精度翻倍，100 次后误差 < 2⁻¹⁰⁰，远超 double 精度），比写 while (right-left > eps) 更安全，不会因 eps 选择不当导致精度问题或死循环。

四、二分算法易错点汇总

#	易错点	正确做法
1	数组无序就直接二分	二分前提是有序，先排序或确认有序
2	`mid = (left+right)/2` 整数溢出	用 `left + (right-left)/2`
3	左闭右闭用 `right = mid`（应为 `mid-1`）	统一区间定义，更新规则与之一致
4	`left = mid` 时 mid 未向上取整 → 死循环	改为 `left + (right-left+1)/2`
5	lower_bound 判断写成 `== target`	应为 `>= target`；upper_bound 为 `> target`
6	二分答案未验证单调性	确认 check 结果随答案单调变化
7	check 函数中忘记剪枝，大数据 TLE	满足条件后尽早 `return true`
8	浮点数二分用整数更新规则	浮点数用 `left=mid`/`right=mid`，不 ±1

五、📝 实战练习

练习题 1（单选题）

题目： 对有序数组 {2, 4, 6, 8, 10, 12, 14} 进行二分查找，查找目标 10，依次比较的元素下标是（下标从 0 开始）（）

A. 3 → 5 → 4
B. 3 → 4 → 5
C. 0 → 3 → 4
D. 0 → 3 → 5

🔑 点击查看答案与解析

答案： A

解析：

初始 left=0, right=6，mid = 0+(6-0)/2 = 3，a[3]=8 < 10，令 left=4
left=4, right=6，mid = 4+(6-4)/2 = 5，a[5]=12 > 10，令 right=4
left=4, right=4，mid=4，a[4]=10 == 10，找到！

比较序列：下标 3 → 5 → 4。

练习题 2（判断题）

题目： 二分查找可以在任何数组上使用，不管数组是否有序。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 二分查找的前提是序列必须有序。只有序列有序，才能通过比较中间元素判断目标在哪一半，从而砍掉另一半搜索空间。如果数组无序，每次比较后无法确定目标的位置，二分就失去了意义。

🍎 生活比喻：二分查找就像查字典——字典是按拼音排序的，所以你可以从中间开始翻，根据拼音决定往前还是往后翻。如果字典是乱序的，你就只能一页一页找了（线性查找）。

练习题 3（单选题）

题目： 计算 mid = (left + right) / 2 可能会有什么问题？（）

A. 结果不对
B. 整数溢出
C. 死循环
D. 编译错误

🔑 点击查看答案与解析

答案： B

解析：

当 left 和 right 都很大时（比如都接近 INT_MAX），left + right 可能超过 int 的范围，导致整数溢出，结果变成负数或不可预期的值。

安全写法：mid = left + (right - left) / 2

数学上等价，但 right - left 不会溢出，所以更安全。

选 B。

💡 记忆口诀：加起来会爆，减一下就好。写 mid 就用 left + 差值的一半。

练习题 4（单选题）

题目： 左闭右开区间 [left, right) 的二分查找，循环条件和右边界更新分别是？（）

A. while(left <= right) 和 right = mid - 1
B. while(left < right) 和 right = mid
C. while(left < right) 和 right = mid - 1
D. while(left <= right) 和 right = mid

🔑 点击查看答案与解析

答案： B

解析：

左闭右开 [left, right) 的特点：

right 指向的位置不包含在搜索区间内
循环条件：left < right（相等时区间为空）
目标在左边时：right = mid（mid 本身也不包含，因为开区间）
目标在右边时：left = mid + 1

选 B。

🔥 高频考点：两种区间写法对比是选择题常客
左闭右闭：while(left <= right)，right = mid - 1
左闭右开：while(left < right)，right = mid

练习题 5（单选题）

题目： 在有序数组 {1, 3, 3, 3, 5, 7} 中，lower_bound(3) 返回的元素下标是？（）

A. 1
B. 2
C. 3
D. 4

🔑 点击查看答案与解析

答案： A

解析：

lower_bound(target) 返回第一个 ≥ target 的元素的位置。

数组中有三个 3，分别在下标 1、2、3 处。第一个 ≥ 3 的位置就是第一个 3 的位置，即下标 1。

选 A。

💡 区分两个 bound：
lower_bound：第一个 ≥ target 的位置（下界）
upper_bound：第一个 > target 的位置（上界）
两者之差就是 target 出现的次数。

练习题 6（单选题）

题目： 下列哪种问题最适合用二分答案来解决？（）

A. 求数组的最大值
B. 求两个数的和
C. 求"满足条件的最小值"，且条件具有单调性
D. 求斐波那契数列第 n 项

🔑 点击查看答案与解析

答案： C

解析：

二分答案适用于：

问题求"满足条件的最大值"或"满足条件的最小值"
答案具有单调性——如果 x 满足条件，那么比 x 大（或小）的也满足
可以设计一个 check(x) 函数，快速判断 x 是否满足条件
A 错误：遍历一次就行，不需要二分
B 错误：直接相加
C 正确 ✅：这正是二分答案的典型应用场景
D 错误：递推或递归更直接

💡 二分答案口诀："答案有单调性，就能二分猜；猜完验一验，不对往哪调？"

练习题 7（判断题）

题目： 整数二分中，如果 left = mid 且 mid 向下取整，可能会导致死循环。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析：

当区间只剩两个元素 [left, right]，且 left = mid 时：

mid = (left + right) / 2 = left（向下取整）
如果条件满足，left = mid = left（没变！）
下一轮还是一样的状态 → 死循环

解决方法：向上取整，即 mid = left + (right - left + 1) / 2

🔥 关键结论：left=mid 就向上取整，right=mid 就向下取整。 记不住就想：谁等于 mid，就往谁那边"靠"。

练习题 8（编程题）

题目： 请用浮点数二分求 x 的平方根（x ≥ 0），精度要求保留 6 位小数。

输入：一个非负实数 x
输出：x 的平方根，保留 6 位小数

样例输入：2
样例输出：1.414214

提示：可以用 printf("%.6f\n", ans) 来输出。

🔑 点击查看答案与解析

参考答案：

cpp

#include <iostream>
#include <cstdio>
using namespace std;

double sqrt_binary(double x) {
    if (x < 0) return -1;  // 非法输入
    double left = 0, right = x;
    // 特殊处理：x < 1 时，平方根比 x 大
    if (x < 1 && x > 0) right = 1;
    
    // 迭代 100 次，精度足够
    for (int i = 0; i < 100; i++) {
        double mid = (left + right) / 2;
        if (mid * mid <= x) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    double x;
    cin >> x;
    double ans = sqrt_binary(x);
    printf("%.6f\n", ans);
    return 0;
}

解析：

浮点数二分的特点：

不用 ±1，直接 left = mid 或 right = mid
终止条件：迭代固定次数（如 100 次，每次精度翻倍，100 次后精度远超需求）
或者用 right - left > eps 作为循环条件（eps 比如 1e-8）

注意：当 0 < x < 1 时，√x > x，所以右边界要设为 1（比如 √0.25 = 0.5 > 0.25）。

六、📊 考点总结表

考点	重要程度	出题形式	易错点
二分查找前提（有序）	⭐⭐⭐	选择/判断	忘记有序这个前提
左闭右闭写法	⭐⭐⭐⭐⭐	代码填空/程序阅读	while条件和±1搞混
左闭右开写法	⭐⭐⭐⭐	选择/代码填空	right=mid 还是 mid-1
mid 防溢出写法	⭐⭐⭐⭐	选择/代码填空	left + (right-left)/2
lower_bound / upper_bound	⭐⭐⭐⭐	选择/程序阅读	≥ 和 > 搞反
二分答案思想	⭐⭐⭐⭐⭐	编程题	不知道什么时候用二分答案
check 函数设计	⭐⭐⭐⭐	编程题	check函数写不对
整数二分死循环	⭐⭐⭐⭐	选择/代码填空	left=mid时要向上取整
浮点数二分	⭐⭐⭐	选择/编程	不用±1，直接=mid
时间复杂度 O(log n)	⭐⭐⭐⭐	选择	log n 有多快要有概念

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         二分算法 · 必背速记卡               │
├─────────────────────────────────────────────┤
│  1. 二分查找前提：序列必须有序              │
│  2. 时间复杂度 O(log n)，每次砍掉一半       │
│  3. 左闭右闭：[l,r], while(l<=r), ±1       │
│  4. 左闭右开：[l,r), while(l<r), right=mid │
│  5. mid 安全写法：left + (right-left)/2    │
│  6. lower_bound：第一个 ≥ target 的位置    │
│  7. upper_bound：第一个 > target 的位置    │
│  8. 二分答案 = 二分猜答案 + check验证      │
│  9. 二分答案适用：答案有单调性的最优问题    │
│ 10. 最大值最小化 / 最小值最大化 → 想二分   │
│ 11. left=mid → 向上取整防死循环            │
│ 12. right=mid → 向下取整（默认）           │
│ 13. 浮点二分：直接=mid，不用±1             │
│ 14. 浮点终止：迭代100次 或 right-left < eps│
│ 15. 二分精髓：利用单调性，排除不可能的一半  │
└─────────────────────────────────────────────┘

💡 碎片化每日练习，稳住做题手感，慢慢备考远比突击刷题更稳妥。

第5章 二分算法 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

📖 引言 ​

一、二分查找 ​

🔍 核心思想 ​

📐 算法流程（左闭右闭写法） ​

🧩 代码模板：左闭右闭 [left, right] ​

🧩 代码模板：左闭右开 [left, right) ​

⚠️ 两种写法对比（高频考点！） ​

🚫 死循环是怎么来的？ ​

lower_bound 与 upper_bound ​

STL 用法（C++ 标准库） ​

手写 lower_bound / upper_bound 模板 ​

二、二分答案（二分枚举法） ​

🔍 核心思想 ​

📐 通用模板 ​

🧩 经典例题：木材加工 ​

🧩 check 函数设计要点 ​

📌 常见二分答案题型 ​

三、整数二分 vs 浮点数二分 ​

🧩 浮点数二分模板（求平方根） ​

四、二分算法易错点汇总 ​

五、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（判断题） ​

练习题 3（单选题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（编程题） ​

六、📊 考点总结表 ​

⭐ 必背速记卡 ​

第5章二分算法

🎯 本章学习目标

🗺️ 本章知识图谱

📖 引言

一、二分查找

🔍 核心思想

📐 算法流程（左闭右闭写法）

🧩 代码模板：左闭右闭 [left, right]

🧩 代码模板：左闭右开 [left, right)

⚠️ 两种写法对比（高频考点！）

🚫 死循环是怎么来的？

lower_bound 与 upper_bound

STL 用法（C++ 标准库）

手写 lower_bound / upper_bound 模板

二、二分答案（二分枚举法）

🔍 核心思想

📐 通用模板

🧩 经典例题：木材加工

🧩 check 函数设计要点

📌 常见二分答案题型

三、整数二分 vs 浮点数二分

🧩 浮点数二分模板（求平方根）

四、二分算法易错点汇总

五、📝 实战练习

练习题 1（单选题）

练习题 2（判断题）

练习题 3（单选题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（编程题）

六、📊 考点总结表

⭐ 必背速记卡