【算法笔记】二分法保姆级教学（超详细的二分攻略）
打个比方，你玩"猜数字"游戏，对方想的是1-100之间的数字。每次你猜中间值50，对方告诉你"大了"或"小了"，然后继续猜剩余区间的中间值——这就是最朴素的二分思想。
目录
前言：二分法是非常高效的查找方法，在本篇学习结束后，可以掌握绝大多数情况的二分（一定要配合刷题进行巩固啊），同时有兴趣还可以了解一下C++STL中的lower_bound() 和 upper_bound()，相信我学完会有奇效的！！
附赠链接：【C++】STL模板库的lower_bound() 和 upper_bound() 最全使用指南（一篇教会你常用方法！！） -CSDN博客
一、二分法到底是什么？
打个比方，你玩"猜数字"游戏，对方想的是1-100之间的数字。每次你猜中间值50，对方告诉你"大了"或"小了"，然后继续猜剩余区间的中间值——这就是最朴素的二分思想。
正式定义：
二分法（Binary Search）是一种在有序集合中快速定位目标的算法，通过每次比较将搜索范围减半，直到找到目标或确定不存在。
这里有个需要注意的地方：二分法一定要在有序集合中，例如在用二分法找数组中的数时，必须将数组排序！！！
三大核心特征：
-
数据必须有序（或存在单调性）
-
存在明确的分界条件
-
可以通过中间值判断排除一半数据
二、二分法的优势
为什么非要学二分法？难道我直接遍历数组或者集合去找需要的值不行吗？
可以，当然可以，但是当数量比较大的时候，直接暴力遍历的方法容易使得代码效率低下。例如当刷算法题的时候遇到数组长度比较大的时候，直接暴力寻找肯定是行不通的，容易TLE。
先看对比实验：
在10亿有序数据中查找一个数：
-
普通遍历：平均5亿次比较 → 按每秒百万次计算，需要83分钟
-
二分查找：最多30次比较 → 0.00003秒完成
时间复杂度：
-
最坏情况 O(log n)
-
每次操作将数据规模n除以2，直到1为止
-
log₂(10^9) ≈ 30，log₂(2^32)=32
指数爆炸的逆袭：
| 数据规模 | 线性查找次数 | 二分查找次数 |
|---|---|---|
| 100 | 100 | 7 |
| 10,000 | 10,000 | 14 |
| 1,000,000 | 1,000,000 | 20 |
这就是为什么大厂面试必考二分法——海量数据处理的核心技能！
想必大家在写二分题时总遇到为什么这里要 left<=right 才能过，为什么有时候 left = mid +1, right = mid - 1，有时候又 left = mid + 1,right = mid.......这样的困惑在我学二分的时候也经常遇到并且为之困惑，一下代码可以跑，一下又进入死循环一直跳不出。接下来我们就来解决这个困惑！！！
三、二分法的四大金刚
1. 精确查找
标准二分查找，左闭右闭区间 [left, right]
-
初始化：
left = 0,right = n - 1 -
循环条件：
left <= right -
更新方式：
-
若目标在右侧，
left = mid + 1 -
若目标在左侧，
right = mid - 1
-
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (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. 左边界查找
寻找第一个大于等于目标的位置（左闭右开区间） （适合存在重复元素的情况）
左闭右开区间 [left, right)
-
初始化：
left = 0,right = n -
循环条件：
left < right -
更新方式：
-
若目标在右侧，
left = mid + 1 -
若目标在左侧，
right = mid
-
int lowerBound(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即為第一个≥target的位置
}找左边界相当于问："目标值从哪里开始出现？
3. 右边界查找
寻找最后一个小于等于目标的位置 （左闭右开区间）
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 - 1; // left-1即為最后一个≤target的位置
}找右边界相当于问："目标值到哪里结束为止？
4. 特殊场景
（旋转数组找最小值）
int findMin(const vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}这个算法专为旋转排序数组的最小值查找设计，通过二分法高效缩小范围，是处理旋转数组类问题的经典方法。
四、二分法心法口诀
-
区间定义要记牢：闭区间端点含，开区间端点飘
-
循环条件看区间：闭区间用<=，开区间用<
-
mid计算防溢出：l + (r - l)/2 是王道
-
收缩方向看比较：大了往左压，小了往右跑
-
边界检查不能少：找到之后验正身，防止幽灵数据闹
五、二分法例题讲解（附思路）
例题：[P2678 NOIP 2015 提高组] 跳石头 - 洛谷
P2678 [NOIP 2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 L, N ,M ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L >= 1且 N >= M >= 0 。
接下来 行，每行一个整数，第 i 行的整数Di（0 < Di <L） ， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
输入输出样例 #1
输入 #1
25 5 2
2
11
14
17
21输出 #1
4
说明/提示
输入输出样例 1 说明
将与起点距离为 2 和 14 的两个岩石移走后，最短的跳跃距离为 4（从与起点距离 17 的岩石跳到距离 21 的岩石，或者从距离 21 的岩石跳到终点）。
#define int long long
int l, n, m;
int a[50005];
bool check(int mid) {
int now = 0, nex = 0;
int x = 0;//计数
while (nex < n + 1) {
nex++;
if (a[nex] - a[now] < mid) {
x++;
}
else {
now = nex;
}
}
if (x <= m) {
return true;
}
else {
return false;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> l >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[n + 1] = l;
int ans = 0;
int left = 1, right= l, mid;
while(left <= right) {
mid = (left + right) / 2;
if (check(mid)) {
ans = mid;
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << ans << endl;
return 0;
}思路： 本题需要找到最短跳跃距离的最大值，符合二分的应用场景。我们可以套用二分模板，直接二分答案，即最短跳跃距离的最大值。这里需要注意的就是check()函数，通过check函数查找当前跳跃距离需要移走多少块石块，注意当x<=m时返回true。这是因为我们需要找到符合条件的最大值，所以当x=m时，我们仍然需要向右寻找有没有比当前更大的满足条件的值，这是本题的精髓所在。
P1182 数列分段 Section II
题目链接：P1182 数列分段 Section II - 洛谷
本题就不附上题目了（markdown转过来好像有点问题.......），大家请移步到链接查看题目详情吧！！！
那我们直接上思路：这道题是一个典型的二分答案的题，我们要找它的每段和的最大值（看到数组的和我们想到了前缀和，当然这题不用前缀和也可以过），然后就是找二分的边界。每段和的最大值一定比该数组中的最大的一个数大，这个最大数就是二分的left，每段最大和一定不会超过数组中所有数的和，所以right为数组之和。之后就套用二分模板
int n, m;
int a[100005];
int b[100005];
bool check(int mid) {
int k = 0;//记录被分了几组
int left = 0, right = 0;
while (right <= n) {
right++;
if (b[right] - b[left] > mid) {
k++;
left = right - 1;
right--;//当满足if条件时，right在划分的组的右边缘+1的位置，此时如果不减那下一段开始则组的长度为2，可以自己模拟一下，当然也有其他的方式
}
}
k++;//最后一段无论大不大于mid都要算上，是这个题的坑
if (k <= m) {//当k==m时，依旧向左寻找有没有更小的值
return true;
}
return false;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int l = 0, r = 0, mid;
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
r += a[i];
l = max(l, a[i]);
b[i] = b[i - 1] + a[i];
}
while (l < r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;//记录满足条件的答案
r = mid ;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}总结：二分法要注意二分的边界条件，确认left和right，其次就是看该二分题需不需要记录本次满足条件的答案，还是跳出while循环时答案就是mid
六、写二分算法的三个忠告
-
先画图再写代码
在纸上画出数组，标出l/r/mid的位置变化，能避免90%的边界错误 -
测试用例要够狠
必须测试：空数组、单元素、全相同元素、目标不存在、目标在首尾等情况 -
不要死记硬背
理解区间定义和排除逻辑比背模板更重要，遇到变种题才能灵活应对
最后：为什么你总是调不出二分法？
根据我的经验，常见死循环原因就这三个(大佬勿喷！！我是蒟蒻)：
-
区间定义混乱（一会闭一会开）
-
指针移动时没彻底排除mid
-
没处理元素重复的特殊情况
二分虽然很好，但不是什么情况都能用的！！
对于能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。
常见应用场景：最小化最大值问题， 最大化最小值问题
讲了这么多，聪明的你应该对二分有了自己的认识，让我们打开心爱的编译器和OJ，亲自上手试一试吧！！
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
37
0- 0
已为社区贡献1条内容
所有评论(0)