前言
答案属于一个区间，当这个区间很大时，暴力超时。但重要的是这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
模板
模板1
while (l < r)
{
int mid = l + r >> 1; //(l+r)/2
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
模板2：
while (l < r)
{
int mid = l + r + 1 >> 1; //(l+r+1)/2
if (check(mid)) l = mid;
else r = mid - 1;
}
第一个模板是尽量往左找目标，第二个模板是尽量往右找目标。
只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一；
只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一；
模板3：（浮点二分）
while(r-l>1e-5) //需要一个精度保证
{
double mid = (l+r)/2;
if(check(mid)) l=mid; //或r=mid;
else r=mid; //或l=mid;
}
浮点二分就相对简单多了，因为浮点除法不会取整，所以mid，l，r，都不用加1或减1.
函数
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[1000]={};
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
int m;
cin>>m;
for(int i=1;i<=m ;i++)
{
int b;
cin>>b;
cout<<lower_bound(a+1,a+1+n,b)-a<<endl;//第一个大于等于 无 返回>n
cout<<upper_bound(a+1,a+1+n,b)-a<<endl;//第一个大于
cout<<binary_search(a+1,a+1+n,b)<<endl;//有 1，无 0
}
return 0;
}
二分答案
如何判断一个题是不是用二分答案做的呢?
- 答案在一个区间内（一般情况下，区间会很大，暴力超时）
- 直接搜索不好搜，但是容易判断一个答案可行不可行
- 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
此外，可能还会有一个典型的特征：
求...最大值的最小 、 求...最小值的最大。
- 求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid），对应模板1；
- 同样，求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid），对应模板2；