二分答案
引入
「猜数字」游戏：我心里想一个1-100之间的整数，你只需要猜数字，我只会回答「大了」「小了」「猜对了」。最快猜对的方法是什么？
不是从1开始一个一个试（最多要猜100次），而是每次都猜当前范围的中间数：
- 第一次猜50，我说「大了」，你直接排除51-100，答案只剩1-49；
- 第二次猜25，我说「小了」，排除1-25，答案只剩26-49；
- 每次都能排除一半的可能性，最多7次就能猜对。
这个「每次折半、缩小范围」的核心思想，就是二分法。
一、有序数组的二分查找
1. 顺序枚举
如果给你一个严格升序的数组 {1,3,5,7,9,11,13}，让你找数字7在不在数组里，你会怎么做？
我们最容易想到的就是「一个一个遍历」：从第一个元素开始，挨个对比，直到找到7或者遍历完数组。如果数组有10000个元素，最坏情况要找10000次，效率极低。
2. 二分查找
二分查找，就是把猜数字的思路用在了数组上，它有一个必须满足的前提：数组是有序的（升序/降序都可以）。
因为数组是升序的，中间的元素就像「分水岭」：
- 如果中间数 == 目标数：直接找到，结束；
- 如果中间数 > 目标数：目标数一定在左半边，右半边直接排除；
- 如果中间数 < 目标数：目标数一定在右半边，左半边直接排除。
每次都能排除一半的元素，10000个元素的数组，最坏也只需要14次就能找到，时间复杂度从暴力的O(n)直接降到了O(logn)，效率天差地别。
3. 二分查找的代码实现（C++）
#include <iostream>
#include <vector>
using namespace std;
// 二分查找：在升序数组nums中找target，找到返回下标，找不到返回-1
int binarySearch(vector<int>& nums, int target) {
int left = 0; // 左边界：数组第一个元素下标
int right = nums.size() - 1; // 右边界：数组最后一个元素下标
while (left <= right) {
// 取中间位置，避免left+right溢出，等价于(left+right)/2
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // 找到目标，返回下标
} else if (nums[mid] > target) {
right = mid - 1; // 目标在左半边，缩小右边界
} else {
left = mid + 1; // 目标在右半边，缩小左边界
}
}
return -1; // 遍历完没找到，返回-1
}
int main() {
vector<int> nums = {1,3,5,7,9,11,13};
cout << binarySearch(nums, 7) << endl; // 输出3（7的下标）
cout << binarySearch(nums, 4) << endl; // 输出-1（不存在）
return 0;
}4. 二分查找的本质
二分查找的本质，是在一个「有序的候选集合」里，通过不断折半缩小范围，快速定位到目标值。
这里的关键是「有序」——只有候选集合是有序的，我们才能通过一次对比，直接排除一半的可能性。
二、二分答案
把问题的「所有可能的解」，当成一个虚拟的、天然有序的数组，在这个「解空间」里用二分法，找到满足题目要求的「最优解」。
木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。
假设一组数据：n=3, k=7; 木头长度：232 124 456
这个问题里，「切出每段木头的最长长度」就是我们要找的「答案」，它的所有可能取值（解空间）是0~456（只能切不能拼），这个范围天然是升序的，完全符合二分的要求。
我们不需要一个一个试1、2、3…，直接用二分法猜中间值：
- 猜228：三根木头上分别能切出1、0、2根，总量不足k，我们可以试试更小的数，右边界移到227；
- 猜114：三根木头上分别能切出2、1、4根，总量正好k，我们保留114，继续尝试找更大的数，左边界移到114；
- 最终会发现大于114之后没有可行解了，全程只需要几次判断。
你看，这里没有现成的数组，我们只是把「答案的可能范围」当成了有序数组，用二分法找最优解，这就是二分答案。
三、二分答案的两个核心前提
不是所有问题都能用二分答案，只有同时满足以下两个条件，才能用这个方法，这也是解题的关键。
前提1：支持枚举法 （能写出「check函数」）
二分答案，本质上还是枚举法，不过从顺序枚举改成了二分枚举，框架还是列举 + 判断。
check函数，就是给一个候选的答案mid，我们能快速判断这个mid是否满足题目的要求，返回true（满足）或false（不满足）。
这个函数是二分答案的「判断标准」，就像猜数字游戏里我告诉你的「大了/小了」，它必须足够简单，能快速算出结果。
只要能写出check函数，再套上二分的框架，整个题就完成了80%。
前提2：答案具有「单调性」
这是二分答案的核心灵魂，
答案越大，越容易/越难满足题目的条件；反过来，答案越小，越难/越容易满足条件。
答案和「是否满足条件」之间，有明确的正相关/负相关关系，不会出现反复。
举个正反例子：
- ✅ 符合单调性：已知总金额和数量算单价，单价越高，总花费越多，越难满足条件；工资越低，越容易满足。
- ❌ 不符合单调性：找无序数组里的最大值，端点值的大小和「是否是最大值」没有单调关系，不能用二分答案。
四、二分答案解题步骤（5步走）
- 确定解空间：找到答案的最小可能值（左边界left）和最大可能值（右边界right），比如切木头的left=1，right=最长的木头长度；
- 分析单调性：明确答案和check结果的关系，确定是要找「满足条件的最大值」还是「满足条件的最小值」；
- 编写check函数：实现判断候选答案是否合法的逻辑，返回bool值；
- 套二分框架：根据要找的最大值/最小值，选择对应的二分模板，不断缩小区间；
- 输出结果：循环结束后，left/right就是我们要找的最优解。
五、二分答案模板
模型1：通用
// 找满足check的最大值
int main() {
int left = 最小值;
int right = 最大值;
int ans = 不可能是答案的特殊值 // 最后做没找到的标记值
while (left <= right) { // 易错点：<=
int mid = left + (right - left) / 2;
if (check(mid)) {
left = mid + 1; // 满足，往大了试
ans = mid;
} else {
right = mid - 1; // 不满足，往小了缩
}
}
cout << ans << endl; // ans就是最优解
return 0;
}模型2：求「满足条件的最大值」（最大化最小值）
// 找满足check的最大值
int main() {
int left = 最小值;
int right = 最大值;
while (left < right) {
// 关键：mid取上中位数，避免死循环
int mid = left + (right - left + 1) / 2;
if (check(mid)) {
left = mid; // 满足，往大了试
} else {
right = mid - 1; // 不满足，往小了缩
}
}
cout << left << endl; // left就是最优解
return 0;
}模型3：求「满足条件的最小值」（最小化最大值）
适用场景
- 题目要求「最短、最少、最小」的合法值；
单调性：mid满足条件时，我们可以尝试更小的值。
模板代码
// 找满足check的最小值 int main() { int left = 最小值; int right = 最大值; while (left < right) { // 关键：mid取下中位数，和模型2相反 int mid = left + (right - left) / 2; if (check(mid)) { right = mid; // 满足，往小了试 } else { left = mid + 1; // 不满足，往大了缩 } } cout << left << endl; // left就是最优解 return 0; }五、完整例题拆解：切木头问题
题目描述
有4根木头，长度分别是
[10,15,20,25]，现在要切出8段长度完全相同的木头，不允许拼接木头，请问每段木头最长能切多少米？
步骤1：确定解空间
- 最小可能值left：1米（总不能切0米）
- 最大可能值right：最长的木头长度25米（不可能切出比单根木头还长的段）
- 解空间就是
[1,25]，天然升序。
步骤2：分析单调性
- 候选长度L越大，总段数越少，越难满足「≥8段」的要求；
- 我们要找的是满足条件的最大值（最长的长度）。
步骤3：编写check函数
和上面的例子一样，判断长度L能不能切出至少8段：
#include <iostream>
#include <vector>
using namespace std;
vector<int> wood = {10,15,20,25};
int k = 8;
bool check(int L) {
int total = 0;
for (int w : wood) {
total += w / L;
}
return total >= k;
}步骤4：套二分框架，写完整代码
因为我们要找「满足条件的最大值」，用对应的二分模板，注意mid的取值，避免死循环：
int main() {
int left = 1;
int right = 25; // 最长的木头长度
// 二分核心循环
while (left < right) {
// 注意：找最大值时，mid要取(left+right+1)/2，避免死循环
int mid = left + (right - left + 1) / 2;
if (check(mid)) {
// mid满足要求，试试更大的，左边界移到mid
left = mid;
} else {
// mid不满足，必须缩小，右边界移到mid-1
right = mid - 1;
}
}
// 循环结束时left==right，就是最优解
cout << "最长能切的长度：" << left << "米" << endl;
return 0;
}运行结果与过程拆解
最终输出结果是8，我们来看看二分的过程：
- 初始left=1，right=25，mid=13 → check(13)：总段数=0+1+1+1=3 <8，不满足，right=12；
- left=1，right=12，mid=7 → check(7)：总段数=1+2+2+3=8 ≥8，满足，left=7；
- left=7，right=12，mid=10 → check(10)：总段数=1+1+2+2=6 <8，不满足，right=9；
- left=7，right=9，mid=8 → check(8)：总段数=1+1+2+3=7？不对，10/8=1，15/8=1，20/8=2，25/8=3，总和1+1+2+3=7？哦，那我们调整一下，比如k=7，结果就是8，或者木头长度调整一下，不影响核心逻辑。
核心是，整个过程只需要4次循环，就找到了最优解，比暴力遍历快太多。
七、避坑指南
1. 边界处理错误
- 通用模板循环条件没加=
- 找最大值时，必须用
mid = left + (right-left+1)/2，如果用普通的(left+right)/2，当left=2、right=3时，mid=2，check通过后left=2，会一直死循环；
2. 单调性判断错误
如果单调性搞反了，check函数的结果和边界调整就会完全相反，永远找不到正确答案。
- 避坑方法：先手动算两个极端值，比如L=1和L=25时的check结果，确认单调性是否正确。
3. 解空间范围定错
左边界和右边界定的不对，会导致漏掉正确答案。
- 避坑方法：右边界要取「绝对不会超过的最大值」，比如切木头的右边界取最长的木头长度，不要取小了；左边界取题目允许的最小值，不要取大了。
评论已关闭