- gf25055 的博客
《死亡笔记-代码模板》二分
-
gf25055
LV 5
@
2026-4-10 18:49:30
一、二分查找（Binary Search） 典型场景：在 有序数组 中查找目标值，或查找满足某种单调性质的边界。
- 标准二分查找（精确匹配）
// 在有序数组 nums 中查找 target，返回下标，若不存在返回 -1
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) { // 闭区间 [left, right]
int mid = left + (right - left) / 2; // 防溢出
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
2. 查找第一个 ≥ target 的位置（lower_bound）
cpp
// 返回第一个大于等于 target 的下标，若全小于则返回 nums.size()
int lowerBound(vector<int>& nums, int target) {
int left = 0, right = nums.size(); // 左闭右开 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target)
right = mid; // 满足条件，向左收缩
else
left = mid + 1;
}
return left; // 或 right，两者相等
}
3. 查找第一个 > target 的位置（upper_bound）
cpp
// 返回第一个大于 target 的下标
int upperBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target)
right = mid;
else
left = mid + 1;
}
return left;
}
模板要点 区间定义：
精确查找常用闭区间 [left, right]，循环条件 left <= right，更新为 mid ± 1。
边界查找（如 lower_bound）常用左闭右开 [left, right)，循环条件 left < right，更新为 right = mid 或 left = mid + 1。
防溢出：mid = left + (right - left) / 2。
C++ STL 已有函数：lower_bound、upper_bound、binary_search，但手写模板更灵活应对复杂判断条件。
二、二分答案 —— 求最大值最小 核心思想：当问题具有 单调性（即若某个答案 x 可行，则所有 ≥ x 的答案都可行，或反之），我们可以 二分答案，然后用一个判定函数 check(mid) 判断 mid 是否可行，从而收缩区间。
求最大值最小 的一般特征：在满足条件的前提下，使 最大值尽可能小。
通用模板（最大值最小）
// 假设答案范围在 [L, R] 内
int left = L, right = R;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) { // 若 mid 可行，则尝试更小的值
ans = mid;
right = mid - 1;
} else {
left = mid + 1; // 不可行，必须增大 mid
}
}
return ans;
示例：分割数组的最大值（LeetCode 410） 给定非负整数数组和整数 m，将数组分割成 m 个连续子数组，使得子数组和的最大值最小。
bool check(vector<int>& nums, int m, int maxSum) {
int cnt = 1, curSum = 0;
for (int num : nums) {
if (curSum + num > maxSum) {
cnt++;
curSum = num;
if (cnt > m) return false;
} else {
curSum += num;
}
}
return true;
}
int splitArray(vector<int>& nums, int m) {
int left = *max_element(nums.begin(), nums.end()); // 最小可能值
int right = accumulate(nums.begin(), nums.end(), 0); // 最大可能值
int ans = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(nums, m, mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
模板要点 单调方向：check(mid) 返回 true 表示当前最大值 mid 可行，此时我们可以尝试 更小的最大值，因此 right = mid - 1。
答案记录：因为 mid 可行时可能是最终答案，故用 ans 记录，最后返回。
三、二分答案 —— 求最小值最大 典型场景：在满足条件的前提下，使 最小值尽可能大。与上一类方向相反。
通用模板（最小值最大）
int left = L, right = R;
int ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) { // 若 mid 可行，则尝试更大的值
ans = mid;
left = mid + 1;
} else {
right = mid - 1; // 不可行，必须减小 mid
}
}
return ans;
示例：在 D 天内送达包裹的能力（LeetCode 1011） 传送带上的包裹必须按顺序在 D 天内运完，求满足条件的最小运载能力（实际上这题也是求最大值最小，但思路相似）。这里举一个经典的最小值最大问题：Aggressive Cows（POJ 2456）
在一条直线上有 N 个牛棚，给定坐标，要放入 C 头牛，使得最近的两头牛之间的距离尽可能大。
bool check(vector<int>& stalls, int c, int dist) {
int cnt = 1, lastPos = stalls[0];
for (int i = 1; i < stalls.size(); ++i) {
if (stalls[i] - lastPos >= dist) {
cnt++;
lastPos = stalls[i];
if (cnt >= c) return true;
}
}
return false;
}
int maxMinDistance(vector<int>& stalls, int c) {
sort(stalls.begin(), stalls.end());
int left = 1; // 最小可能距离
int right = stalls.back() - stalls[0]; // 最大可能距离
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(stalls, c, mid)) {
ans = mid;
left = mid + 1; // 可行，尝试更大的距离
} else {
right = mid - 1;
}
}
return ans;
}
模板要点 单调方向：check(mid) 返回 true 表示当前最小距离 mid 可行，我们可以尝试 更大的最小值，因此 left = mid + 1。
与最大值最小的区别：仅在于可行时收缩区间的方向不同，本质上都是利用单调性。
四、实数区间二分 典型场景：求方程根、几何问题、概率或精度要求高的最优值。与整数二分不同，循环终止条件通常由 精度 eps 或 固定迭代次数 控制。
通用模板（精度控制）
const double eps = 1e-7; // 精度要求
double left = L, right = R;
while (right - left > eps) {
double mid = (left + right) / 2.0;
if (check(mid)) // 根据单调性决定收缩方向
right = mid; // 或 left = mid
else
left = mid;
}
return left; // 或 right，两者近似相等
示例：计算平方根（或解方程）
double sqrt(double x) {
double left = 0, right = max(1.0, x);
for (int i = 0; i < 100; ++i) { // 固定迭代 100 次，足够安全
double mid = (left + right) / 2.0;
if (mid * mid <= x)
left = mid;
else
right = mid;
}
return left;
}
模板要点 终止条件：
方式一：while (right - left > eps)，注意 eps 应比要求精度再小 1~2 个数量级。
方式二：固定迭代次数（如 100 次），避免精度问题导致的死循环，适用于绝大多数场景。
区间更新：实数二分通常直接 left = mid 或 right = mid，无需 ±1 操作。
五、二分搜索综合练习题模板思路 综合题往往需要将问题 转化成二分判定 的形式，关键步骤为：
识别单调性：是否存在某个临界值，使得一侧全部满足条件，另一侧全部不满足。
设计判定函数 check(mid)：这是二分答案的核心，需要高效（通常 O(n) 或 O(n log n)）判断 mid 是否可行。
确定搜索区间：left 和 right 的初始值，通常为题目给定的明确边界或根据数据范围推算。
选择二分模板：根据是求“最大值最小”还是“最小值最大”确定收缩方向。
常见综合题型分类 题型 典型问题 判定函数设计要点 二分查找变形 搜索旋转排序数组、寻找峰值、有序矩阵第 K 小 利用局部有序性或二分缩小范围 二分答案 + 贪心判定 分割数组、最小化最大和、最大化最小距离、K 次操作后的最大/最小值 在给定 mid 下，用贪心策略模拟计算是否能在约束内完成 二分答案 + 前缀和/双指针 子数组和 ≥ K 的最短长度、第 K 小的子数组和 判定时可能需要滑动窗口、前缀和 + 二分查找 实数二分 高精度求根、三分求极值、几何覆盖问题 固定迭代次数，判定函数为数学计算 交互式二分 猜数字、第一个错误的版本 调用外部 API 作为 check 条件 综合示例：K 次操作后最大化的最小值 给定数组 nums，每次操作可以将某个元素加 1，最多操作 K 次，求操作后数组最小值最大是多少。
bool check(vector<int>& nums, long long k, int target) {
long long need = 0;
for (int num : nums) {
if (num < target)
need += target - num;
if (need > k) return false;
}
return need <= k;
}
int maxMinAfterKOperations(vector<int>& nums, int k) {
int left = *min_element(nums.begin(), nums.end());
int right = left + k; // 最大值不可能超过这个
int ans = left;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(nums, k, mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
六、二分常见易错点总结 易错点 说明与解决方法 死循环 整数二分更新时，确保每次区间至少缩小 1。常用 left = mid + 1 或 right = mid - 1。 mid 计算溢出 始终用 left + (right - left) / 2，而非 (left + right) / 2。 区间开闭混乱 选定一种区间定义（闭区间 [L,R] 或左闭右开 [L,R)）并贯彻到底。 判定函数复杂度太高 二分答案的判定函数应尽可能 O(n) 以内，否则总时间可能超限。 答案未记录导致丢失 在可行时用 ans = mid 记录，避免最后 left/right 不一定是正确答案的情况。 实数二分精度问题 优先使用固定迭代次数（如 100 次），或设 eps 为要求精度的 1/100。