二分
一般来讲我们可能会在以下情况用二分：
- 求单调函数的零点，或者找个值（二分查找）
- 求一堆东西的最小值最大（或是最大值最小）是多少（二分答案）
- 很难直接算出答案，但是很好判定答案合不合法
- 对于单峰函数，可用二分导函数来代替三分
二分查找
二分是一种可以在\(O(chlogm)\)（m为数据规模，ch为判断状态合法性check()函数时间复杂度）时间复杂度内求解问题的方法，主打一个分治思想，每次将搜索范围减半。
我们以二分查找引入。
有一个有序序列，二分查找的思想如下：
1.定义L,R,mid代表答案在[L,R]内，中点为mid
2.查找mid所在值，如果mid大于查找值，搜索范围定为[L,mid]，如果mid小于查找值，搜索范围定为[mid,R]，如果查找到了，则返回L。
3.将mid重新设为中点，并调至2。
二分查找的时间复杂度是\(O(logn)\)顺序查找的时间复杂度是\(O(n)\)
代码的话在这：
//二分查找(递归)
//list是待查找的数组，查不到就返回-1代表无解
int binarySearch(int list[],int left,int right,int number)
{
if(list==NULL) return -1;
int mid=(right+left)/2;
if(left>right)return -1;
if(number==list[mid])return mid;//检查中间
else if(number>list[mid]) binarySearch(list,mid+1,right,number);//递归搜右边
else binarySearch(list,left,mid-1,number);//递归搜左边
}
//二分查找(循环)
int binarySearch(int list[],int left,int right,int number)
{
if(list==NULL) return -1;
while(left<right)
{
int mid=(right+left)/2;
if (list[mid] == number) return mid;//看看中间是不是
else if (number > list[mid]) left=mid+1;//搜右边
else if (number < list[mid]) right=mid-1;//搜左边
}
return -1;
}
二分答案
二分答案嘛，就是像二分查找一样，只是判断改了，模板：
while(l<r)
{
mid=(l+r)/2;
if (check(mid)) r=mid;
else l=mid+1;
}
check一般是贪心(写循环、推公式)或DP。
具体应用
比如方程求根啦：
[NOIP2001 提高组] 一元三次方程求解
题目描述
有形如：\(a x^3 + b x^2 + c x + d = 0\) 这样的一个一元三次方程。给出该方程中各项的系数（\(a,b,c,d\) 均为实数），并约定该方程存在三个不同实根（根的范围在 \(-100\) 至 \(100\) 之间），且根与根之差的绝对值 \(\ge 1\)。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 \(2\) 位。
提示：记方程 \(f(x) = 0\)，若存在 \(2\) 个数 \(x_1\) 和 \(x_2\)，且 \(x_1 < x_2\)，\(f(x_1) \times f(x_2) < 0\)，则在 \((x_1, x_2)\) 之间一定有一个根。
输入格式
一行，\(4\) 个实数 \(a, b, c, d\)。
输出格式
一行，\(3\) 个实根，从小到大输出，并精确到小数点后 \(2\) 位。
样例 #1
样例输入 #1
1 -5 -4 20
样例输出 #1
-2.00 2.00 5.00
【题目来源】
NOIP 2001 提高组第一题
这提示明摆着疯狂暗示我们二分写check()啊，按提示二分即可：
#include<bits/stdc++.h>
#define db double
using namespace std;
db a,b,c,d,f1,f2;
int cnt=0;
db check(db x){return a*x*x*x+b*x*x+c*x+d;}
int main()
{
cin>>a>>b>>c>>d;
db l,r,mid;
for(db i=-100;i<=100;++i)
{
f1=check(i);
f2=check(i+1);
if(!f1){printf("%.2lf ",i);cnt++;}
if(f1*f2<0)
{
l=i,r=i+1;
while(r-l>=0.001)
{
mid=(l+r)/2;
if (check(mid)*check(r)>0) r=mid;
else l=mid;
}
printf("%.2lf ",r);
cnt++;
}
if (cnt==3) break;
}
return 0;
}
小学奥数啦：
小车问题
题目描述
甲、乙两人同时从 A 地出发要尽快同时赶到 B 地。出发时 A 地有一辆小车，可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样，且小于车的速度。问：怎样利用小车才能使两人尽快同时到达。
输入格式
仅一行，三个实数，分别表示 AB 两地的距离 \(s\)，人的步行速度 \(a\)，车的速度 \(b\)。
输出格式
两人同时到达 B 地需要的最短时间，保留 \(6\) 位小数。
样例 #1
样例输入 #1
120 5 25
样例输出 #1
9.600000
数据规模与约定
对于 \(100\%\) 的数据，保证 \(0 \leq s, a, b \leq 10^9\)。
这题不想推公式可以直接二分爽推。
首先，每个人都要坐一次车，而且两个人要同时到达，这样才能使总时间最短。
那么，我们设起点为\(A\)，终点为\(B\)，小车先带甲开到\(C\)点后，甲下车走到\(B\)点，同时小车掉头与已经走到\(D\)点的乙相向而行，相遇于点\(E\)，最后小车带乙向\(B\)开去，和甲同时到达。(拗口拗口阿巴阿巴)
先设\(AC=S\)
那么:
车从\(A\)到\(C\)的时间：\(T_{A→C}=\frac{S}{V_{car}}\)
车与乙汇合所用时间：\(T_{B,D→E}=\frac{S-T_{A→C}\times V_{man}}{V_{car}+V_{man}}\)
甲所用时间：\(T_{1}=T_{A→C}+\frac{S_{AB}-S}{Vman}\)
乙所用时间：\(T_{2}=T_{A→C}+ T_{B,D→E}+\frac{S_{AB}-(T_{A→C}+T_{B,D→C})\times V_{man}}{V_{car}}\)
然后二分\(C\)点啦：
#include<bits/stdc++.h>
using namespace std;
int main()
{
double s,s1,s2,v1,v2,t1,t2,p;
double a,b;
scanf("%lf%lf%lf",&s,&v1,&v2);
s1=0;
s2=s;
do
{
p=(s1+s2)/2.0;
a=p/v2;
b=(p-a*v1)/(v1+v2);
t1=a+(s-p)/v1;
t2=a+b+(s-(a+b)*v1)/v2;
if(t1<t2)s2=p;
else s1=p;
}
while (fabs(t1-t2)>1e-8);
printf("%.6lf",t1);
return 0;
}
一堆最小值里求最大值啦：
[NOIP2015 提高组] 跳石头
题目背景
NOIP2015 Day2T1
题目描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。
接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i\,( 0 < D_i < L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
样例 #1
样例输入 #1
25 5 2
2
11
14
17
21
样例输出 #1
4
提示
输入输出样例 1 说明
将与起点距离为 \(2\) 和 \(14\) 的两个岩石移走后，最短的跳跃距离为 \(4\)（从与起点距离 \(17\) 的岩石跳到距离 \(21\) 的岩石，或者从距离 \(21\) 的岩石跳到终点）。
数据规模与约定
对于 \(20\%\)的数据，\(0 \le M \le N \le 10\)。
对于 \(50\%\) 的数据，\(0 \le M \le N \le 100\)。
对于 \(100\%\) 的数据，\(0 \le M \le N \le 50000,1 \le L
\le 10^9\)。
硬找所有可能的石头方案，让最短跳距尽可能长，一眼\(O(n^{2})\)肯定超时。
那就试试暴力 (其实是小贪心) +二分查找答案\(O(nlogn)\)咯
跳距离和石头成“反比”，跳距越大，石头越少，跳距越小，石头越多嘛。
直接在[0,L]上二分查找一个跳距\(x\)，用贪心看看这个跳距下还能留下多少石头。
\(L\)的大小是\(10^{9}\)之内，求个\(log_{2}(L)\)直接暴降，\(AC\)，爽！
#include<bits/stdc++.h>
using namespace std;
int D[50010];
int L,M,N;
bool check(int x)//check用循环写个小贪心
{
int s=0,num=0;
D[N+1]=L;
for(int i=1;i<=N+1;i++)
{
if(D[i]-s<=x)num++;//记一下某个跳距时，能留下来的石头数量
else s=D[i];
}
if(num>M)return 1;//石头留多了，加税！继续增跳距，减石头
else return 0;//石头少了或者刚刚好，地主家都没余粮了，就别减了
}
void solve()
{
cin>>L>>N>>M;
for(int i=1;i<=N;i++)cin>>D[i];
int l=0,r=L;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
}
int main()
{
int T=1;
while(T--) solve();//多测改单测的写法
return 0;
}
当然，还有三分啦：
【模板】三分 | 函数
题目描述
给定 \(n\) 个二次函数 \(f_1(x),f_2(x),\dots,f_n(x)\)（均形如 \(ax^2+bx+c\)），设 \(F(x)=\max\{f_1(x),f_2(x),...,f_n(x)\}\)，求 \(F(x)\) 在区间 \([0,1000]\) 上的最小值。
输入格式
输入第一行为正整数 \(T\)，表示有 \(T\) 组数据。
每组数据第一行一个正整数 \(n\)，接着 \(n\) 行，每行 \(3\) 个整数 \(a,b,c\)，用来表示每个二次函数的 \(3\) 个系数，注意二次函数有可能退化成一次。
输出格式
每组数据输出一行，表示 \(F(x)\) 的在区间 \([0,1000]\) 上的最小值。答案精确到小数点后四位，四舍五入。
样例 #1
样例输入 #1
2
1
2 0 0
2
2 0 0
2 -4 2
样例输出 #1
0.0000
0.5000
提示
对于 \(50\%\) 的数据，\(n\le 100\)。
对于 \(100\%\) 的数据，\(T<10\)，\(\ n\le 10^4\)，\(0\le a\le 100\)，\(|b| \le 5\times 10^3\)，\(|c| \le 5\times 10^3\)。
三分板子题，二分是三个变量L，mid，r分两段，三分就用四个变量L，Lmid，Rmid，R分三段
#include<bits/stdc++.h>
using namespace std;
vector<double> a(10005),b(10005),c(10005);
int n;
double f(double x)
{
double maxx=-0x7fffffff;
for(int i=1;i<=n;i++)
maxx=max(maxx,a[i]*x*x+b[i]*x+c[i]);
return maxx;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
double L=0,R=1000;
while(L+1e-11<R)
{
double Lmid=L+(R-L)/3;
double Rmid=R-(R-L)/3;
if(f(Lmid)<=f(Rmid))R=Rmid;
else L=Lmid;
}
cout<<fixed<<setprecision(4)<<f(L)<<endl;
}
int main()
{
int T;
cin>>T;
while(T--)
solve();
return 0;
}
洛谷二分入门题单：https://www.luogu.com.cn/training/111
牛客二分+三分+01分数规划题单：https://ac.nowcoder.com/acm/contest/22353
再找点洛谷二分题，支持边学边练（参考大佬call_of_silence的题单）
P1102：easy。
P1676：贪一手。
P1083：前缀和优化check，不会前缀和别写。 （不过能看到这里的应该都学会差分前缀和了吧）
P1314：直接模拟，二分出参数\(W\)，再把\(W\)带入求得\(|s-y|_{minn}\)，check()里前缀和优化，时间复杂度\(O(nlogn)\)。
P1678：排个序，二分查找，比较刚好比自己大一点的那个大学与刚好比自己小一点的大学做差比较绝对值，累加。
P1824：先排序，二分最近距离。一旦距离大于check()的x，那么牛的数量++，最后比较牛的总数与当前距离满足要求可以住下的牛的总数。
P2249：二分查找，lower_bound()与upper_bound()的应用。
P1163：小数（实数）二分板子题，二分每个月的月利息，然后纯模拟。
P2390：和例题那个石头思路有点想，不过这题其实使用贪心，可能还好想一点。
P2920：原数组按结束时间升序排序，然后二分最早开始的时间，不过贪心做更爽。
P4058：二分时间，注意木料必须是一整棵树 （卡我好久）
P1182&P2855&P3853：三道和例题跳石头的类题摆一起，三倍经验，二分最小的最大距离，每一次check()扫一遍，距离大于check(x)的x，就记录一下，最后判断按照这个距离需要分几段，与题目要求进行比较。（其中第一道和原题差不多，后两道变了一点）
P2440&P1577：类题，双倍经验，只不过一道是整数，一道是实数二分，二分长度len。
P1570：小贪心，每一次check需要排序+贪心，贪一手，时间复杂度\(O(nlogn)\)(差不多，还有一部分复杂度不想算了)
P1873：二分高度，时间复杂度\(O(nlogn)\)。
P1843：模拟，二分最少用的天数，在一定天数内由自然晒干的continue，对于每一个干不了的使用机器（注意机器只能以整数天使用，你每天可以烘干5点的机器去干一件一点的衣服也需要一天），所以除的时候向上取整，最后判断天数是否可以接受。
P1661：二分+并查集混题，可以速学一下并查集板子来做这题。
P3743：小数二分，类似P1843一样处理，电用完了就找充电宝，这里的充电宝支持小数时间的充电。
P2985：二分最不开心的一天的开心值，模拟，输出时如果还有糖果没有吃完那么默认没吃完的糖果留在最后一天吃。
P8666：多维差分板子题，也可以用二分（麻烦，其实可以用这题把多维差分复习一下，没学的直接学了再写）。
P1281：计算总页数，二分答案（思路类似前面的三倍经验）——计算出最多的人需要的最短的时间，然后以这个最短的时间为标准再扫一遍，处理出每一个人需要的做的页数，排序，保证最前面的人做的活最少。
P3611：二分答案，check()模拟的时候可能需要用到优先队列priority_queue<int,vector<int>,greater<int>>（又叫大根堆），简称pq，pq也是赛时贪心常客了，可以先混个脸熟。
P1542：直接模拟，小数二分，注意快递员是只能在\(l_{1}\)到\(r_{1}\)之间送货。
P4447：贪心+二分查找。
P3957：难得找到个check()里面是DP的典题。
P1663：要二分找到最小的，使阴影区间存在的\(y\)值，关键在写check()， 藏了道初中数学题 ，计算出\(n-1\)条斜线的解析式，然后小数二分，二分最低的\(y\)值，对于每一个解析式，带入\(y\)解出不等式，根据\(a[i]\)的正负可以得出解得区间“方向”，进而确定需要记录的区间边界\(l\)和\(r\)，用两个全局变量数组\(l[i]\)，\(r[i]\)记录，然后找到最大左边界和最小右边界，最后判断是否有解，有解则说明当前的\(y\)值是可以接受的。最后输出就可以了。
P3933：给一个矩阵，你能把它分成两个部分，分割线需要是阶梯状，求使得两个部分极差最大值的最小值（是不是又见到这个东西了？一堆东西“最小值最大”或“最大值最小”果断二分）。四个方向每个方向都要一次二分答案。