二分法
整数二分
有单调性一定能二分，但是能二分的题目不一定有单调性
注意点：刚开始可都写mid=（l+r）/2，若check之后r=mid，则保留之前写的，若check之后l=mid，则将前面改为mid=（l+r+1）/2
二分法模板
//二分法模板
//区间[1,r]被划分为[1,mid]和[mid+1,r]时使用
int bsearch_1(int l,int r)//l与r分别为左右边界点
{
while(l<r)
{
int mid = l + r >> 1;//相当于l+r的值除以2取整
if(check(mid)) r = mid;//check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
//区间[1,r]被划分为[1,mid-1]和[mid,r]时使用
int bsearch_1(int l,int r)//l与r分别为左右边界点
{
while(l<r)
{
int mid = l + r + 1>> 1;//相当于l+r的值除以2取整
if(check(mid)) l = mid;//check()判断mid是否满足性质
else r = mid - 1;
}
return l;
}
例题
数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
代码儿
#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
while(m--)
{
int x;
scanf("%d",&x);
int l=0,r=n-1;
//此处为寻找起始位置，即为左边界，此处使用的是模板1
while(l<r)
{
int mid = l + r >>1;
if(q[mid]>=x) r = mid;//则说明mid在右半边，而答案在左半边，要注意此处可能可以取到等于mid
else l = mid+1;//否则mid在左半边，更新l的值
}
if(q[l]!=x) cout <<"-1 -1"<<endl;//如果最后q[l]的值不等于答案x，则无解
else
{
cout<< l <<" ";
//此处使用的是模板2
int l=0,r=n-1;
while(l<r)
{
int mid = l + r + 1>>1;
if(q[mid]<=x) l=mid;
else r=mid-1;
}
cout << l << endl;
}
}
return 0;
}
浮点数二分
每次必能缩小一半，所以无需处理边界，当区间的长度很小时，例如r-l<=10e-6,则可将边界r或l所对应的数视为答案
#include<iostream>
using namespace std;
int main()
{
double x;
cin>>x;
double l=0,r=x;
while(r-l>1e-8)
{
double mid = (l+r)/2;
if(mid*mid>=x) r=mid;
else l=mid;
}
printf("%lf
",l);//输出l或者r都可以
//若题目让我们保留四位小数，上面精度写1e-6,五位小数，写1e-7,六位小数，为1e-8
return 0;
}