二分法的常见运用

· · 个人记录

1 二分查找

可以说，这是二分的第一步，也是非常单纯的二分，目的很简单，缩小范围。

1.1 最常见的模型

1.1.1 猜数字

你猜一个整数，告诉你大了小了。
很显然每次猜已知范围的中间数。

1.1.2 函数零点问题

这个详见数学书。在这里长话短说。

Step 1：该函数取一左端x_{1}，右端x_{2}；发现f(x_{1})* f(x_{2})<0；
Step 2：取 x_{1} 和 x_{2} 的平均值 x_{mid}；寻找 x_{1} 和 x_{2} 哪个与 x_{mid} 的积 <0；
Step 3：重复Step 2，直到 x 的范围的精度符合要求。

1.2 特征

参数： 只有两个未知数。将自变量 x 代入函数，导出因变量 y 并与条件相比较。

时间复杂度：

## 2 二分答案 ### 2.0 与二分查找的区别 **参数：** 超出两个未知数。 **条件：** 第三个未知数有极强的顺序性或线性。 **目的：** 由于第三个未知数与题目所求相关，然而对于两个未知数的算法在与第三个未知数线性依次计算的话会超时。于是需要压缩第三个数，减小时间复杂度。 **时间复杂度：** $O(lgn)* O$(基础算法复杂度) ### 2.1 例 [P1083·NOIP2012 借教室](https://www.luogu.org/problem/show?pid=1083) [P1462 通往奥格瑞玛的道路](https://www.luogu.org/problemnew/show/P1462) ## 3 二分判定性问题 ### 3.1 例 [P2115·USACO14MAR 破坏Sabotage](https://www.luogu.org/problemnew/show/P2115)