STO#y总#Or2
二分：check函数＋两模板；（前提是已经排好序才能二分）
假设有一个总区间，经由我们的 check 函数判断后，可分成两部分，
这边以o作 true，.....作 false 示意较好识别
如果我们的目标是下面这个v，那么就必须使用模板 1(r=mid)
................vooooooooo
假设经由 check 划分后，整个区间的属性与目标v如下，则我们必须使用模板 2(l=mid)
oooooooov...................
所以下次可以观察 check 属性再与模板1 or 2 互相搭配就不会写错啦
1.【深基13.例1】查找
题目链接：https://www.luogu.com.cn/problem/P2249
秒杀题，没啥解释的，直接上代码：
1 #include <bits/stdc++.h>
2 using namespace std;
3 int n,m;
4 const int N=1e6+10;
5 int q[N];
6 int main()
7 {
8 scanf("%d%d",&n,&m);
9 for(int i=1;i<=n;i++)scanf("%d",&q[i]);
10 while(m--)
11 {
12 int x;
13 scanf("%d",&x);
14 int l=1,r=n;
15 while(l<r)
16 {
17 int mid=l+r>>1;
18 if(q[mid]>=x)r=mid;
19 else l=mid+1;
20 }
21 if(q[l]!=x)printf("%d ",-1);
22 else printf("%d ",l);
23 }
24 }
2.进击的奶牛
题目链接：P1824 进击的奶牛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10;
4 int q[N];
5 int n,m;
6 bool check(int x)
7 {
8 int cnt=1,tmp=q[1];
9 for(int i=2;i<=n;i++)
10 {
11 if(q[i]-tmp>=x)
12 {
13 cnt++;
14 tmp=q[i];
15 }
16 }
17 return cnt>=m;
18 }
19 int main()
20 {
21 cin>>n>>m;
22 for(int i=1;i<=n;i++)cin>>q[i];
23 sort(q+1,q+1+n);
24 int l=0,r=1e9;
25 while(l<r)
26 {
27 int mid=l+r+1>>1;
28 if(check(mid))l=mid;
29 else r=mid-1;
30 }
31 cout<<l;
32 }
3.跳石头
原题链接：P2678 [NOIP2015 提高组] 跳石头 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路
一眼看到题目中的这一句话：使得选手们在比赛过程中的最短跳跃距离尽可能长，当出现最小值最大或最大值最小或求最大值、最小值时，就可以考虑一下二分了。
很显然，这道题我们求的是最短距离，所以我们二分的就是最短距离。
首先验证答案具有单调性：拿走的石头越多，最短跳跃距离越大，这就叫答案的单调性。
然后进行实现。我们假设最短跳跃距离为mid，接着我们写一个check函数，判断一下这个mid是否合法，如果合法，就尝试找一找有没有一个值比mid更大（l=mid），如果不合法，就把mid减小（r=mid-1）。
check函数：我们遍历一遍每一块石头，累计出有多少块石头之间的间隔<=mid,如果超过m个，就不合法，如果小于等于m，就合法。
1 #include <bits/stdc++.h>
2 using namespace std;
3 int s,n,m;
4 const int N=1e6+10;
5 int q[N];
6 bool check(int x)
7 {
8 int cnt=0;int last=0;
9 for(int i=1;i<=n;i++)
10 {
11 if(q[i]-last<x)cnt++;//
12 else last=q[i];
13 }
14 return cnt<=m;
15 }
16 int main()
17 {
18 scanf("%d%d%d",&s,&n,&m);
19 for(int i=1;i<=n;i++)scanf("%d",&q[i]);
20 int l=1,r=1e9+10;
21 q[n+1]=s;
22 n+=1;
23 while(l<r)
24 {
25 int mid=l+r+1>>1;
26 if(check(mid))l=mid;
27 else r=mid-1;
28 }
29 cout<<l;
30 }
4.P1024 [NOIP2001 提高组] 一元三次方程求解
原题链接：P1024 [NOIP2001 提高组] 一元三次方程求解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
观察100/0.01=1e4 爆搜！！！这题我是真不知道咋二分（复杂捏）qwq
1 #include <bits/stdc++.h>
2 using namespace std;
3 double a,b,c,d;
4 int main()
5 {
6 scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
7 for(double i=-100;i<100;i+=0.01)
8 if(fabs(i*i*i*a+i*i*b+i*c+d)<1e-4)//必须加绝对值，因为当趋近于0时候在x轴上下均符合
9 printf("%.2lf ",i);
10 }
5.P1873 [COCI 2011/2012 #5] EKO / 砍树
原题链接：P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题一定要LL啊（哭），开1e6就够了，开1e9当时直接炸了...
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 LL q[1000005];
5 LL m,n;
6 typedef long long LL;
7 bool check(LL x)
8 {
9 LL sum=0;
10 for(LL i=0;i<n;i++)
11 {
12 if(q[i]>x)sum+=q[i]-x;
13 }
14 return sum>=m;
15 }
16 int main()
17 {
18 cin>>n>>m;
19 for(LL i=0;i<n;i++)cin>>q[i];
20 LL l=1,r=1e9;
21 while(l<r)
22 {
23 LL mid=l+r+1>>1;
24 if(check(mid))l=mid;
25 else r=mid-1;
26 }
27 cout<<l;
28 }
6.三分法（反正不会三分，，看还有人用粒子群优化（Particle Swarm Optimization,PSO）做的）
我只会求导qwq
原题链接：P3382 【模板】三分法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
浮点数二分不用照顾边界！！！安心二分就行了！！！不用加一减一的麻烦自己！！！
1 #include <bits/stdc++.h>
2 using namespace std;
3 int n;
4 double l,r;
5 double a[15];//存系数
6 bool check(double x)
7 {
8 double lim=0;
9 for(int i=0;i<n;i++)
10 {
11 lim+=a[i]*pow(x,i);
12 }
13 return lim>0;
14 }
15 int main()
16 {
17 cin>>n>>l>>r;
18 for(int i=n;i>=0;i--)
19 {
20 double x;
21 cin>>x;
22 if(i==0)break;
23 a[i-1]=x*i;
24 }
25 while(r-l>1e-7)
26 {
27 double mid=(l+r)/2;//浮点数二分不需要+1，本来就是准确的，虽然写的时候加了然后就卡了好久....
28 if(check(mid))l=mid;
29 else r=mid;//浮点二分直接取中点，不用减一 要是-1就会有可能造成死循环
30 }
31 cout<<fixed<<setprecision(5)<<l;
32 }
二分算是浅浅掌握了，呼~呲饭
标签：二分,int,double,LL,mid,ACM,week2,check From： https://www.cnblogs.com/Zac-saodiseng/p/16852031.html