首先简单介绍一下二分法
度娘的定义：
对于区间\([a,b]\)上连续不断且\(f(a)\cdot f(b)<0\)的函数\(y=f(x)\)，通过不断地把函数\(f(x)\)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。
使用二分需要满足哪些条件？
根据度娘的定义,只要满足所求函数函数\(f(x)\)在闭区间\([a,b]\)上连续,且\(f(a)\cdot f(b)<0\),则\(f(x)=0\)存在根
由此,使用二分需要满足两个条件:
1.边界确定在一个区间\([a,b]\)中
2.函数在区间\([a,b]\)内具有单调性
满足以上两个条件,就可以考虑进行二分
二分的时间效率如何？
对于一个区间长度为\(n\)的函数,每次范围缩小为原来的一半,时间复杂度为\(O(\log n)\)，\(\log n\)有多大呢,举个例子,当\(n=1e18\)(绝大多数不使用高精度题目的数据的最大上限),\(\log n\approx 60\) (一个不到100的小常数 ),因此二分的时间效率还是挺可观的
oi界中二分一般只有两种题型:整数二分和实数二分，其中整数二分考察较多。
本文重点讲解整数二分
整数二分
一般的使用场景就是在给定单调序列中查找某个大于\(x\)或大于等于\(x\)的第一个值
可以直接使用STL中的upper_bound()和lower_bound(),网上的诸多大佬的博客已经讲述的比较详尽,蒟蒻在此不多赘述
而对于更高级的情况需要手写判断情况的check()函数,较为常见的两个模板放在下面
while(l<r)
{//写法1
int mid=l+r>>1;
if(check(mid))
{
l=mid+1;
...//维护xxx
}
else
{
r=mid;
...//维护xxx
}
...//维护xxx
}
while(l<r)
{//写法2
int mid=l+r+1>>1;
if(check(mid))
{
l=mid;
...//维护xxx
}
else
{
r=mid-1;
...//维护xxx
}
...//维护xxx
}
以上两种写法,在acwing 中有明确的讲解,蒟蒻在这里放上链接供客官观看。
在洛谷许多的题解中,也有下面这样的写法,也是比较综合好用的一种写法
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))
{
l=mid+1;
...//维护xxx
}
else
{
r=mid-1;
...//维护xxx
}
...//维护xxx
}
个人认为选择哪种写法,一般是每个人的不同习惯,只要写法正确,习惯用一个就不要随意更改，赫题解的时候也要改变成自己习惯的写法。
对于check()函数,我认为是通过做题量积累出来的经验,注意模板要和check()函数匹配,有时需要根据不同情况加以修改
具体例题讲解
P2678跳石头(二分)
P4343自动刷题机(二分)
P1902刺杀大使(二分+bfs/dfs/最小生成树+并查集判断连通性)
P1314聪明的质监员(二分+前缀和维护)
P1083借教室(二分+差分维护)
实数二分
相比整数二分,实数二分的模板更简单,没有一些繁琐和复杂的操作，因为不会存在卡整数而产生的死循环，唯一需要注意的地方就是精度eps的选取。
while(r-l>eps)
{
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
具体例题讲解
P1024一元三次方程求解(整数二分)
参考资料：oi wiki，acwing，百度,算法竞赛进阶指南(罗勇军 郭卫斌著)