【算法笔记】二分查找 && 二分答案（超详细解析，一篇让你搞懂二分）

---

前言

二分查找应该算是是很多人入门的第一个算法吧，无论是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的数，并返回其下标
int bsearch_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的数，并返回其下标
int bsearch_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的数，并返回其下标
int bsearch_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的数，并返回其下标
int bsearch_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 例题

（一）P2249 【深基13.例1】查找

这题就是道二分查找的板题，相信大家都能写出来，直接奉上AC代码

#include<iostream>
using namespace std;
const int N=1000010;
int a[N],x,q,n;int main(){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<<" ";}return 0;
} 

（二）P1102 A-B 数对

思路：给出了C，我们要找出A和B。我们可以遍历数组，即让每一个值先变成B，然后二分找对应的A首次出现位置，看是否能找到。
如果找到A，那就二分找最后出现的位置，继而，求出A的个数，即数对的个数。
注意：
int： 2的30次方 ;long long：2的60次方，因此要开long long（不开long long 见祖宗…）

ACcode

#include<iostream>
#include<algorithm>
using namespace std;const int N=200010;
long long a[N],n,c,res,st;int main(){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就继续 else continue;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;return 0;
} 

三、二分答案

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.二分答案模板

尽量往左找答案

//求最小的最大值
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}return l;
}

尽量往右找答案

//求最大的最小值
int bsearch_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>
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N];bool check(int x){int sum = 0;for (int i = 1; i <= n;i++){if(a[i]>x)sum += a[i] - x;if(sum>=m)return true;}return false;
}int main(){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;elser = mid - 1;}cout << l << endl;return 0;
}

(二）P1182 数列分段 Section II

解题思路：

这就是一道求最小的最大值的题

1.找有单调性的答案区间：
要求最大值最小，则该值必定大于数列中的最大值（最大值单独为一段的时候），最大值则为数列中所有数之和​。所以最大值的区间 left=数列中的最大值，right=数列的所有数之和。
2.设计check函数
需要两个变量，sum表示当前这段中的数字总和，cnt表示数列目前分了多少段，因为从a[0]一开始就是第一段，cnt最少是一段，所以初始赋值为1，具体见代码注释。
3.套模板
ACcode

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
long long n, m, a[N], maxn, sum;bool check(long long x){long long 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+1cnt++;}}if(cnt<=m)return true;return false;
}int main(){cin >> n >> m;for (int i = 0; i < n;i++){cin >> a[i];maxn = max(maxn, a[i]);//maxn表示数组中元素的最大值sum += a[i];//sum表示数列中所有元素之和}long long l = maxn, r = sum;while(l<r){long long mid = l + r >> 1;if(check(mid))//更新区间r = mid;elsel = mid + 1;}cout << l;return 0;
}

（三）P1824 进击的奶牛

解题思路

这就是一道求最大的最小值的题

1.找有单调性的答案区间：
l为1，就是紧挨着，r为a[n-1]-a[0];
2.设计check函数
和上一道题差不多，具体看注释
3.套模板
ACcode

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, m, a[N], maxn;bool check(long long 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)return true;return false;
}int main(){cin >> n >> m;for (int i = 0; i < n;i++){cin >> a[i];}sort(a, a + n);//二分的题，一定不要忘了排序long long l = 1, r = a[n - 1] - a[0];//最小值为1，就是紧挨着 ，最大值为最后一个坐标减第一个坐标while(l<r){long long mid = l + r + 1 >> 1;if(check(mid))l = mid;elser = mid - 1;}cout << l;return 0;
}

四、浮点数二分（实数二分）

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.000000

ACcode

#include<iostream>
using namespace std;
int main()
{double x;cin>>x;double l=-100,r=100;//根据题目范围 开三次方根 估计答案大概范围while(r-l>1e-8){double mid=l+r>>1;if(mid*mid*mid>=x)r=mid;elsel=mid;}printf("%.6lf\n",l);return 0;
}

五、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>
using namespace std;
int main(){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。

int bsearch_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。

int bsearch_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;
}