【算法笔记】二分查找 && 二分答案 （超详细解析，一篇让你搞懂二分）
【算法笔记】二分查找 && 二分答案（超详细解析，一篇让你搞懂二分）
目录
- 【算法笔记】二分查找 && 二分答案（超详细解析，一篇让你搞懂二分）
- 前言
- 一、什么是二分查找？为什么要用二分查找？
- 二、二分查找写法
- 三、二分答案
- 四、浮点数二分（实数二分）
- 五、lower_bound 和 upper_bound
- 六、练习题
- 七、总结
前言
二分查找应该算是是很多人入门的第一个算法吧，无论是ACM还是蓝桥杯都是必学的算法，很多人都觉得其非常简单，但它真的那么简单吗？ Knuth 大佬（发明 KMP 算法的那位）曾说过：
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…(思路很简单，细节是魔鬼)
本文将为大家详细讲解二分查找的原理和使用场景
并且，我们就是要深入细节，我将从while循环中该不该带=、mid该不该+1等地方分析这些细节的差异及出现差异的原因，保证你能灵活准确的写出二分查找算法。
一、什么是二分查找？为什么要用二分查找？
1.1.基本概念
二分查找，也称为折半查找（Binary Search），是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将目标值与数组中间的元素进行比较，如果目标值小于中间元素，则在数组的左半部分继续查找，否则在右半部分查找，不断缩小搜索范围，直到找到目标值或确定目标值不存在为止。二分查找的时间复杂度为O(logn)，即查找效率较高。1.2.为什么要用二分查找
想在数组中查找一个元素，最朴素的做法便是从头到尾遍历数组中的每个元素，该操作时间复杂度为O(n),当数组元素较多时会TLE，而二分查找只需O(logn)的时间复杂度便可完成对有序数组的查找，大大提高了算法的效率。
1.3.图解
1.4.优缺点
优点：
- 比较次数少，查找速度快，效率高
缺点：
- 必须要求待查表为有序表
- 插入删除困难
二、二分查找写法
2.1.while(l<r)
尽量向左找目标
//在a数组中寻找第一个>=x的数，并返回其下标intbsearch_1(int l,int r){while(l < r){int mid = l + r >>1;//或写成(l+r)/2if(a[mid]>=x) r = mid;else l = mid +1;}return l;//因为while循环当l==r时终止，return r也可以}尽量向右找目标
//在a数组中寻找最后一个<=x的数，并返回其下标intbsearch_2(int l,int r){while(l < r){int mid = l + r +1>>1;//或写成(l+r+1)/2if(a[mid]<=x) l = mid;else r = mid -1;}return l;//因为while循环当l==r时终止，return r也可以}2.2.while(l<=r)
尽量向左找目标
//在a数组中寻找第一个>=x的数，并返回其下标intbsearch_1(int l,int r){int res=0x3f3f3f3f//可以先将res设置为一个很大的数，如果while循环终止后res没变，便没找到while(l <= r){int mid = l + r >>1;//或写成(l+r)/2if(a[mid]>=x){ r = mid-1; res=mid;}else l = mid +1;}return res;}尽量向右找目标
//在a数组中寻找最后一个<=x的数，并返回其下标intbsearch_2(int l,int r){int res=0x3f3f3f3f//可以先将res设置为一个很大的数，如果while循环终止后res没变，便没找到while(l <= r){int mid = l + r >>1;//或写成(l+r)/2if(a[mid]<=x){ l = mid+1; res=mid;}else r = mid -1;}return res;}2.2.代码细节解析
首先，区间是有单调性的，我们想查找目标值第一次出现的位置，如果查到一个值比目标值大，就把右半边丢掉，因为右半边肯定也比目标值大；同样，如果查到值比目标值小，那就丢掉左半边。
1.l+r>>1什么意思？
这个是位运算写法，将整数类型的二进制表示右移一位，等同于(l+r)/2，注意，double类型不适用这一点。
2. 循环条l<=r 和l<r 有什么区别？
本质上没什么区别，只是循环终止条件不同，个人建议用l<r，代码简便，清晰明了。
3.为什么当循环条件为l<=r时要用res来记录答案，为l<r时直接返回l或``r即可？
因为当循环条件为l<r时，在循环的过程中，可以发现当mid满足条件时l和r的更新方式都是l=mid、r=mid，而不是l=mid+1、r=mid-1，在这个过程l/r已经替代res完成了记录并更新答案的过程，便不需要额外再用一个变量来存储答案，当循环终止时l==r,此时的l/r就在答案位置，直接输出l/r即可；而当循环条件为l<=r时，每次mid满足条件l和r都会更新到mid的下一位置，所以此时就需要一个res变量存储满足条件的位置（mid）并不断更新，res最后一次更新的值便是答案，并且while(l<=r)终止时l和r不相等，不方便通过l和r返回答案
4.为什么当循环条件为l<r时mid的表达式是（l+r+1)/2?什么时候需要加1什么时候不需要加？
至于什么时候需要加1，就记住就可以了，
当while循环条件写的是l<r时，如果是l=mid,就需要加1，如果是r=mid就不需要。
至于为什么呢，大家都知道/是向下取整，那么可以想一个极端的时候，当l=r-1的时候，此时区间为[l,r], mid=(l+r)/2=(l+l+1)/2=l, l=mid,更新后区间变为[mid,r],也就是[l,r]，和原来一模一样，然后就会陷入无尽的死循环；而如果+1的话，mid=(l+r+1)/2=(l+l+1+1)/2=r,区间变为[r,r]循环终止，避免了死循环。而正因为/是向下取整，所以当r=mid时不+1也会直接更新成[l,l]，所以不用加。
5.为什么当循环条件为l<r 时会出现l=mid/r=mid的时候，什么时候l=mid+1/r=mid-1,什么时候l=mid/r=mid?
这个要看实际情况，可以参考我代码上的两种情况，我分别给大家详细解析一下
//在a数组中寻找第一个>=x的数 a={1,2,2,2,3,3,3,4,5} x=3 初始状态： l=0 r=8 mid=(l+r)/2=4，答案区间[0,8] 此时a[mid]=a[4]=3>=3(符合条件），这个时候的mid也是满足答案的， 所以答案区间应该更新为[0,4]而不是[0,4-1]，所以应该是r=mid而不是r=mid-1 其实我这个样例显而易见，如果r=mid-1,那么直接就WA了，你直接把正确答案给扔出区间了 我们继续对[0,4]进行二分，此时mid=(0+4)/2=2; 此时的a[mid]=a[2]=2<x,此时的mid不满足答案，这个数和它之前的数就可以直接排除了， 那他就不应该在答案区间中继续二分,下一次我们应该从mid的下一个数开始找 即答案区间应更新为[2+1,4],所以应该是l=mid+1 这个时候如果你写的是l=mid,那么会直接喜提死循环 //在a数组中寻找最后一个<=x的数 和上面的其实一样，我再举个样例 a={0,1,1,1,2,2,3,4,5} x=2 初始状态： l=0 r=8 mid=(l+r)/2=4，答案区间[0,8] 此时a[mid]=a[4]=2<=2(符合条件），这个时候的mid也是满足答案的， 所以答案区间应该更新为[4,9]而不是[4+1,9]，所以应该是l=mid而不是l=mid+1 然后这时候你可以顺势把上面写的(l+r)/2 改成 (l+r+1)/2//不改一会就死循环 这又是一个极端的样例，如果l=mid+1,那么直接就WA了，你直接把正确答案给扔出区间了 继续二分，[4,9],mid=(4+9+1)/2=7; 此时a[mid]=a[7]=4>x ,不满足答案，直接排除，从它的下一个数开始找 答案区间更新为[4,7-1]，所以是r=mid-1 同样，如果你写的是l=mid,那么喜提死循环 如果题里是找第一个>x的数，就直接把>=改成> 就好了，灵活一点
2.3 例题
这题就是道二分查找的板题，相信大家都能写出来，直接奉上AC代码
#include<iostream>usingnamespace std;constint N=1000010;int a[N],x,q,n;intmain(){ cin>>n>>q;for(int i=1;i<=n;i++) cin>>a[i];while(q--){ cin>>x;int l=1,r=n;//左右边界 while(l<r)//因为是找第一次出现的位置，那就是尽量往左来，就用模板1 {int mid=l+r>>1;if(a[mid]>=x) r=mid;//判断条件，如果值大于等于目标值，说明在目标值右边，尽量往左来else l=mid+1;}if(a[l]!=x){//如果找不到这个值 cout<<-1<<' ';continue;} cout<<l<<" ";}return0;}（二）P1102 A-B 数对
思路：给出了C，我们要找出A和B。我们可以遍历数组，即让每一个值先变成B，然后二分找对应的A首次出现位置，看是否能找到。
如果找到A，那就二分找最后出现的位置，继而，求出A的个数，即数对的个数。
ACcode
#include<iostream>#include<algorithm>usingnamespace std;constint N=200010;longlong a[N],n,c,res,st;intmain(){ cin>>n>>c;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);//先排序 for(int i=1;i<n;i++)//遍历每一个B {int l=i+1,r=n;//寻找A第一次出现的位置，使得A-B=C while(l<r)//因为是第一次出现，尽量往左找{int mid=l+r>>1;if(a[mid]-a[i]>=c) r=mid;//判断：在目标值的右边，满足，往左来else l=mid+1;}if(a[l]-a[i]==c) st=l;//能找到C就继续 elsecontinue; l=st-1,r=n;//查找A最后出现的位置 while(l<r)//因为是最后一次出现，尽量往右找{int mid=l+r+1>>1;if(a[mid]<=a[st]) l=mid;//判断：在目标值的左边，满足，往右去else r=mid-1;} res+=l-st+1;//最后出现的位置减首次出现的位置就是区间长度，即A的个数 } cout<<res;return0;}三、二分答案
3.1.什么是二分答案
对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check函数），看是否对应的那个量达到了需要的大小，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。
这么解释可能比较抽象，大家可以回想一下高中做选择题的时候，如果不会做，这个时候你是不是会运用排除法，把四个选项挨个往里带，如果A B C D是递增的，有时候是不是你把C带进去不对的同时把D也同时排除了
举个例子 3+（）=7 A.2 B.4 C.9 D.11 E.12 F.17... 不会就选C(bushi),我们先从C代，把C带进去都>7了，那C后面的选项一定都是错的,可以直接排除 这个过程其实就是一个简单的二分答案，排除答案的过程就是check的过程
3.2.二分查找和二分答案有什么区别
二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案
由二分查找类比到二分答案
3.3.二分答案模板
尽量往左找答案
//求最小的最大值intbsearch_1(int l,int r){while(l < r){int mid = l + r >>1;if(check(mid)) r = mid;else l = mid +1;}return l;}尽量往右找答案
//求最大的最小值intbsearch_2(int l,int r){while(l < r){int mid = l + r +1>>1;if(check(mid)) l = mid;else r = mid -1;}return l;}你会发现二分答案其实只是把二分查找的条件改成了check，这个就是二分的通用模板，可以直接套板子应对绝大部分二分问题
3.4.什么时候该使用二分答案
1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
4、关键词：求…最大值的最小值 、 求…最小值的最大值、求满足条件下的最小（大）值、 求最靠近一个值的值、 求最小的能满足条件的代价…
3.5.怎样二分答案
1.找具有单调性的答案区间（l= …,r=…）
如何理解答案的单调性呢？可以见下图，该图表示一个区间，从左到右要实现的代价逐渐增高，我们要在这个区间里找到一个代价最小的满足条件的答案。观察图可以发现，位于答案左边的区间不满足条件，位于答案右边的区间满足条件，像这种要么一边不满足，要么一边都满足的现象就是答案的单调性。
答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：
移动石头的个数越多，答案越大（NOIP2015跳石头）。
前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。
满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。
满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。
时间越长，越容易满足条件（NOIP2012疫情控制）。
2.设计check函数
这个具体题目具体分析，可以看例题感受一下，究其根本还是要多做题，无他，唯手熟尔
3.套模板不用我多说了吧
3.6.例题
（一）P1873 [COCI 2011/2012 #5] EKO / 砍树
这道题目本质上就是要求一个最大高度的问题，使得砍到的树的总长度满足条件，拿样例 1 举例，展示出来就是这样的：
假设 ans 是满足条件的最大高度，那么在图片中展示就是这样的：
大于 ans 的高度，不满足条件，小于ans 的高度，都满足条件，这样的答案具有 单调性，所以考虑使用 二分答案 。
解题思路：
1.找有单调性的答案区间：
我们要求一个满足条件的最大高度，那么答案的范围就应该是从 0 到树的最大高度 height，也就是 [0,height]
2.设计check函数
可以看出来这题是尽量向右（向上）找答案，这道题我们可以用一个变量sum存储得到的总长度，如果 sum 大于等于 m 就直接返回true，否则返回false.
3.套模板
ACcode
#include<iostream>usingnamespace std;constint N =1e6+10;int n, m, a[N];boolcheck(int x){int sum =0;for(int i =1; i <= n;i++){if(a[i]>x) sum += a[i]- x;if(sum>=m)returntrue;}returnfalse;}intmain(){ cin >> n >> m;int height =0;for(int i =1; i <= n;i++){ cin >> a[i]; height =max(height, a[i]);//记录最大高度}int l =0, r = height;while(l<r){int mid = l + r +1>>1;if(check(mid))//判断是否达到要求的木材总量m，更新区间 l = mid;else r = mid -1;} cout << l << endl;return0;}
解题思路：
这就是一道求最小的最大值的题
1.找有单调性的答案区间：
要求最大值最小，则该值必定大于数列中的最大值（最大值单独为一段的时候），最大值则为数列中所有数之和。所以最大值的区间 left=数列中的最大值，right=数列的所有数之和。
2.设计check函数
需要两个变量，sum表示当前这段中的数字总和，cnt表示数列目前分了多少段，因为从a[0]一开始就是第一段，cnt最少是一段，所以初始赋值为1，具体见代码注释。
3.套模板
ACcode
#include<iostream>usingnamespace std;constint N =1e5+10;longlong n, m, a[N], maxn, sum;boolcheck(longlong x){longlong sum =0, cnt =1;//sum表示当前这段中的数字总和，cnt表示数列目前分了多少段for(int i =0; i < n;i++){if(sum+a[i]<=x)//判断a[i]是否可以放入当前这段 sum += a[i];// //sum+a[i]不超过mid则可以继续连接else{ sum = a[i];//否则a[i]自起一段，数列总段数cnt+1 cnt++;}}if(cnt<=m)returntrue;returnfalse;}intmain(){ cin >> n >> m;for(int i =0; i < n;i++){ cin >> a[i]; maxn =max(maxn, a[i]);//maxn表示数组中元素的最大值 sum += a[i];//sum表示数列中所有元素之和}longlong l = maxn, r = sum;while(l<r){longlong mid = l + r >>1;if(check(mid))//更新区间 r = mid;else l = mid +1;} cout << l;return0;}（三）P1824 进击的奶牛
解题思路
这就是一道求最大的最小值的题
1.找有单调性的答案区间：l为1，就是紧挨着，r为a[n-1]-a[0];
2.设计check函数
和上一道题差不多，具体看注释
3.套模板
ACcode
#include<iostream>#include<algorithm>usingnamespace std;constint N =1e5+10;longlong n, m, a[N], maxn;boolcheck(longlong x){int idx =0, cnt =1;//index为当前坐标,cnt为奶牛数量 for(int i =1; i < n;i++){if(a[i]-a[idx]>=x){//判断a[i]和当前坐标之前的差值 idx = i;//条件成立，更新坐标，奶牛数量+1 cnt++;}}if(cnt>=m)returntrue;returnfalse;}intmain(){ cin >> n >> m;for(int i =0; i < n;i++){ cin >> a[i];}sort(a, a + n);//二分的题，一定不要忘了排序longlong l =1, r = a[n -1]- a[0];//最小值为1，就是紧挨着 ，最大值为最后一个坐标减第一个坐标while(l<r){longlong mid = l + r +1>>1;if(check(mid)) l = mid;else r = mid -1;} cout << l;return0;}什么时候往左找，什么时候往右找？
精髓
精髓就在于：尽可能这三个字。
例子1
比如数组 a [ ] = { 0 , 1 , 1 , 1 , 2 , 2 , 3 , 4 , 5 } a[] = \{0, 1, 1, 1, 2, 2, 3, 4 , 5\} a[]={0,1,1,1,2,2,3,4,5}
找最后一个 ≤ 2 \le 2 ≤2 的数， m i d = 4 mid = 4 mid=4, 指向第一个2，满足条件，这个时候你是不是想再往右找看看右面还有没有满足的？
因为要找 最后一个，也就是尽可能向右找。
就 l = m i d l = mid l=mid
例子2
再来看砍树那道题。
他要 M M M的木材，还要尽可能少砍一点，也就是尽可能高。
他如果锯片在 a [ m i d ] a[mid] a[mid]的地方就已经能得到 m m m的木材了，那就继续往上升看看能不能更高点，就 l = m i d l = mid l=mid（继续往上搜）。
总结
他要最大值尽可能小
既然是尽可能小
那就是满足条件时 r = m i d r=mid r=mid，看看能不能再小点
满足条件的时候就往不满足条件那个方向移，不满足条件的时候就往满足条件的方向移
满足条件的时候就是 i f ( c h e c k ( m i d ) ) if(check(mid)) if(check(mid)) 后面跟的
这就是二分答案。
四、浮点数二分（实数二分）
4.1.模板
思路和整数二分一样，区别是浮点型二分不需要注意边界问题（也就是不需要+1/-1）
while(r-l>1e-5)//需要一个精度保证{double mid =(l+r)/2;if(check(mid)) l=mid;//或r=mid;else r=mid;//或l=mid;}4.2 例题
（一）数的三次方根
题目描述
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00输出样例：
10.000000ACcode
#include<iostream>usingnamespace std;intmain(){double x; cin>>x;double l=-100,r=100;//根据题目范围 开三次方根 估计答案大概范围while(r-l>1e-8){double mid=(l+r)/2;if(mid*mid*mid>=x) r=mid;else l=mid;}printf("%.6lf\n",l);return0;}五、lower_bound 和 upper_bound
这两个是C++的STL库封装的两个二分查找函数，使用时需要加上头文件
#include<algorithm>使用方法和sort函数很像，可以用greater< type > 重载，也可以自定义比较函数，具体可以翻阅相关博客，在这里只简单介绍一下基本的使用方法
upper_bound
upper_bound(begin, end, value)//在从小到大的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个大于value的数，找到返回该数字的地址，没找到则返回end。upper_bound(begin, end, value, greater<int>())//在从大到小的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个小于value的数，找到返回该数字的地址，没找到则返回end。lower_bound
lower_bound(begin, end, value)//在从小到大的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个大于等于value的数，找到返回该数字的地址，没找到则返回end。lower_bound(begin, end, value, greater<int>())//在从大到小的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个小于等于value的数，找到返回该数字的地址，没找到则返回end。注意，返回的是地址，不是下标，也不是数值！！！
如果你直接输出，那么你会得到这样一串东西（地址）
接下来举个例子，讲解一下在实际中怎么用
#include<iostream>#include<algorithm>usingnamespace std;intmain(){int a[]={1,2,3,3,3,4,4,5,6};int x =3;//查找第一个>x的元素,并输出其下标 cout <<upper_bound(a, a +9, x)- a;//输出 5（下标）// 查找第一个>x的元素,并输出其数值auto i =upper_bound(a, a +9, x); cout <<*i;//输出4（数值）//查找第一个>=x的元素,并输出其下标 cout <<lower_bound(a, a +9, x)- a;//输出 2（下标）// 查找第一个>=x的元素,并输出其数值auto j =lower_bound(a, a +9, x); cout <<*j;//输出3（数值）}该函数的前两个参数及其重载方式和sort（）函数差不多，如果不了解的话可以去学习一下sort（）的相关语法，类比一下就懂了
六、练习题
相信大家已经正式入门二分了，接下来可以做几道题练习一下，题解后续更新。
P1678 烦恼的高考志愿
P1163 银行贷款
P8647 [蓝桥杯 2017 省 AB] 分巧克力
P1024 [NOIP2001 提高组] 一元三次方程求解
P2440 木材加工
P1577 切绳子
P2678 [NOIP2015 提高组] 跳石头
1460. 我在哪？
102. 最佳牛围栏
…
七、总结
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
intbsearch_1(int l,int r){while(l < r){int mid = l + r >>1;if(check(mid)) r = mid;else l = mid +1;}return l;}当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
intbsearch_2(int l,int r){while(l < r){int mid = l + r +1>>1;if(check(mid)) l = mid;else r = mid -1;}return l;}
