二分法及模板
1. 种类介绍
二分法按照适用的类型不同，可以分为：整数二分和浮点数二分。不同的类型，模板也各不相同。下面会分情况进行讨论。
2. 二分法的本质
二分法的本质并不在于单调性。如果某个问题具有单调性的性质，那么这个问题一定可以用二分法来解决。如果某个问题利用了二分法来解决，这个问题不一定具有单调性的性质。那么，二分法的本质是什么呢？二分法的本质就是寻找边界。下面根据二分法的类型不同，来分别讨论它们的思想。
3. 整数二分思想
如果存在某个区间q,我们假定在这个区间q上存在某种性质。使得，绿色的区间都满足这种性质，而红色的区间都不满足这种性质。（也可以相反）（绿色和红色的区间没有交点）那么，二分法就可以把绿色和红色区间的边界给二分出来。对于以上两种区间的边界，分别对应着不同的整数二分模板。
4. 整数二分模板
我们假设寻找红色区间的边界。
1. 首先，先要计算整个区间的中间位置。即，mid = l+r+1/2。[加一的目的是为了避免死循环。]
2. 检查mid点是否满足某种性质。（这里的性质，我们假设为是否满足红色区间的情况）如果条件为true，那么mid点就在红色区间之中，那么寻找红色区间边界的范围，由原来的[l,r]=>[mid,r]。(这里需要注意的是，这个区间包含mid，因为mid有可能取到红色区间的边界)。如果条件为false,那么mid点就在绿色区间之中，那么寻找红色区间边界的范围，由原来的[l,r]=>[l,mid-1]。（这里需要注意的是，由于mid在绿色区间，mid最多取在红色区间边界的下一个位置，mid是绝对取不到红色区间的边界）（再次强调一下，由于是整数二分，因此红色区间和绿色区间并没有交点）。
接下来，我们假设寻找绿色区间的边界。
1. 首先，先要计算整个区间的中间位置。即，mid = l+r/2。
2. 检查mid点是否满足某种性质。（这里的性质，我们假设为是否满足绿色区间的情况）如果条件为true，那么mid点就在绿色区间之中，那么寻找绿色区间边界的情况，由原来的[l,r]=>[l,mid]。(这里需要注意的是，这个区间包含mid，因为mid有可能取到绿色区间的边界)。如果条件为false,那么mid点就在红色区间之中，那么寻找绿色区间边界的范围，由原来的[l,r]=>[mid+1,r]。（这里需要注意的是，由于mid在红色区间，mid最多取在绿色区间边界的前一个位置，mid是绝对取不到绿色区间的边界）（再次强调一下，由于是整数二分，因此红色区间和绿色区间并没有交点）。
讨论完上述情况之后，我们来看一下整数二分的两个模板。
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}
那么，我们如何选择这两种模板呢？
1. 首先，先编写（考虑）check(mid)函数，看看区间的更新方式如何。
2. 根据区间的更新方式不同，我们就可以考虑使用不同的整数二分模板。
综合上述来看，二分法实际上就是在寻找边界（答案）。寻找边界的过程中，通过把区间缩小一半，来定位到答案所在的区间（每次定位区间时，这个区间内一定是有答案的）。当区间长度为1时，那么这个区间里面的数就是答案。需要注意的是，二分法是一定有解的。（所谓无解的情况，一般都跟题目有关，而跟二分法无关。即，通过二分法而寻找到的解，不符合这个题目的要求，因此无解）下面通过一个例题来说明整数二分。
5. 整数二分的例题
https://www.acwing.com/activity/content/problem/content/823/
由于这道题需要寻找所求元素的起始位置和中止位置。那么对于起始位置和中止位置的寻找正好可以利用二分法来求解。
对于所给的案例：1 2 2 3 3 4 如果我们需要寻找元素3的起始位置。那么我们可以定义某一种性质，使得可以划分为两个区间，且这两个区间是没有交点的。这个性质就是大于等于3。如果我们需要寻找3的终点位置。那么我们也可以定义某一种性质，使得满足上述需求。这个性质就是小于等于3。假设，这道题中3这个元素不存在的话，那么当我们按照大于等于3这个性质去寻找3的左边界（起始位置）的话，二分法寻找到的是大于3的最小的数，因此二分法是一定有解的，只不过二分法所寻找到的解不满足题意。（在这种情况下，应该输出-1 -1）
根据上述的情况，我们可以将3推广到任意数字。
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
int n,m;
int x;
int q[100010];
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&q[i]);
}
while(m--){
scanf("%d",&x);
//先寻找指定数的左边界
int l = 0;
int r = n-1;
while(l < r){
int mid = (l+r) >> 1;
if(q[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
//当循环结束时，区间长度为1，此时l==r,q[l]或者q[r]都是要寻找的边界
//如果寻找的边界，不满足要求，那么该元素在数组中不存在
if(q[l] != x){
printf("-1 -1\n");
continue;
}else{
//输出左边界
printf("%d ",l);
//继续寻找指定数的右边界
int l = 0;
int r = n-1;
while(l < r){
int mid = (l+r+1) >> 1; //需要注意，不同情况
if(q[mid] <= x){
l = mid;
}else{
r = mid - 1;
}
}
//输出右边界
printf("%d\n",l);
}
}
return 0;
}
6. 浮点数二分的思想
浮点数二分相对于整数二分比较简单。这是因为，相对于整数二分来讲，浮点数二分每一次都可以精确的将区间分为一半。而整数二分具有整除的性质，因此有时不太能将区间分为一半，因此就需要处理边界问题，而浮点数二分就没有这个问题。其余的思想都跟整数二分相似。唯一需要注意的是，当采用整数二分时，当二分之后的区间长度为1时，区间内部元素就是答案。而浮点数二分没有整除的性质，因此区间长度就不太好确定，我们可以计算当区间长度(r-l)小于一定的误差时，该区间内部的元素（l或r）就是答案。 浮点数二分可以用来求解平方根或立方根问题。
这里有一个经验：如果题目要求保留x位小数的话，那么误差就是1e-(x+2)。
下面给出浮点数二分的模板：
7. 浮点数二分的模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
8. 浮点数二分的习题
https://www.acwing.com/problem/content/792/
首先利用二分法的思想来做这道题
1. 我们需要考虑如下的四种情况来进行解题。
1. 如果数x为正数且不在0和1之间。
2. 如果数x为负数且不在-1和0之间。
3. 在0和1之间的数x。
4. 在-1和0之间的数x。
下面来依次进行讲述。
2. 首先，我们都以mid的立方>=x为性质进行解释，接下来依次解释上述四种情况。
1. 将区间设置为l=0,r=x。在这种情况下，x的三次方根不可能大于x小于0。如果mid的立方大于等于x的话，那么mid一定位于x三次方根的右侧，因此可以将区间缩小为l=0,r=mid。否则，l=mid,r=x。具体的例子可以参考：求x=1000的立方。
2. 将区间设置为l=x,r=0。在这种情况下，x的三次方根不可能大于0小于x。如果mid的立方大于等于x的话，那么mid一定位于x三次方根的右侧，因此可以将区间缩小为l=x,r=mid。否则,l=mid,r=0。 具体的例子可以参考：求x=-1000的立方。
3. 将区间设置为l=0,r=1。在这种情况下，x的三次方根不可能大于1小于0。但是x的三次方根有可能大于本身。例如，x=0.001的三次方根为0.1。所以将区间设置为l=0,r=x是不可取的。如果mid的立方大于等于x的话，那么mid一定位于x三次方根的右侧，因此可以将区间缩小为l=0,r=mid。否则，l=mid,r=x。具体的例子可以参考：求x=0.001的立方。
4. 将区间设置为l=-1,r=0。在这种情况下，x的三次方根不可能大于0小于-1。但是x的三次方根有可能小于本身。例如，x=-0.001的三次方根为-0.1。所以将区间设置为l=x,r=0是不可取的。如果mid的立方大于等于x的话，那么mid一定位于x三次方根的右侧，因此可以将区间缩小为l=0,r=mid。否则，l=mid,r=x。具体的例子可以参考：求x=-0.001的立方。
将上述的情况解释完之后，我们就可以按照思路做题了。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main(){
double n;
double l,r;
scanf("%lf",&n);
//处理输入的数大于等于0的情况
if(n >= 0){
//如果输入的数在0和1之间，那么区间要改变
if(n>=0 && n <=1){
l = 0;
r = 1;
}else{ //输入的数在0和1之外
l = 0;
r = n;
}
while((r-l) > 1e-8){ //这个地方比较的是区间的长度
double mid = (l+r)/2;
if(mid*mid*mid >= n){
r = mid;
}else{
l = mid;
}
}
//处理输入的数小于0的情况
}else{
//如果输入的数在-1和0之间，那么区间要改变
if(n >= -1 && n <= 0){
l = -1;
r = 0;
}else{ //输入的数在-1和0之外
l = n;
r = 0;
}
while(abs(l-r) > 1e-8){ //这个地方比较的是区间的长度，这就是去绝对值的原因
double mid = (l+r)/2;
if(mid*mid*mid >=n){
r = mid;
}else{
l = mid;
}
}
}
printf("%.6lf",l);
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。