二分法

~~不要问我为什么写，考试考了没想出来~~

0.定义/时间复杂度

字面意思，在有序序列中二分查找元素/答案。

由于是二分，所以复杂度为 $\Omicron(\log _ 2 n)$ ，但是一般我们不写底数，因为 $(\log _ a x)' = \frac{1}{x \ln a}$ ，当 $x \to \infty$ 时， $a$ 对运行时间的影响比较小，所以一般不写，而且在 OI 中 $a$ 一般等于 $2$ 。

1.二分查找

一般都不手写，STL 里面有 lower_bound 和 upper_bound，一般够了。不行还有 set 等容器

但是还是写个模板吧

1
int a[] = {...} // a 中元素有单调性
2
int l = 1,r = n;
3
while(l < r)
4
{
5
    //int mid = (l + r) / 2;
6
    int mid = l + (r - l) >> 1; //等价，但更快 & 防溢出
7
    if(a[mid] <= x)
8
        l = mid;
9
    else
10
        r = mid;
11
}
12
ans = l;

2.二分答案

(1) 整数二分

当答案具有一个分界点，即满足 $\exist p,[l,p) \text{ is legal},[p,r] \text{ is illegal}$ 时，我们就可以用二分答案来将复杂度降低到 $\Omicron(\log n)$ 。

具体就是将求解的过程转化为将答案带入判断是否合法的过程，如果合法，则计入答案，同时根据题目调整端点以求更优的答案，否则调整端点使答案合法。

(2) 实数二分

退出条件变为 $r - l \lt eps$ ，其中 $eps \to 0$ 。

虽然是基础算法，但用的挺广的，题型变化也很灵活，多练。

3. 三分

这个更偏数学一点，是拿来求一个单峰或单谷函数的极值的。

我们考虑一个函数取得极大值的充要条件，就是在极值点导数为 $0$ 。某些情况下我们可以用手动求导加二分来求出极值点，但是更多的时候，是没有给你可以求导的解析式的。

这个时候，我们从导数的定义入手，就是 $\frac{\text{d}}{\text{d} x} f(x) = \lim \limits _ {\text{d} x \to 0} \frac{f(x + \text{d} x) - f(x)}{\text{d}x}$ ，所以，我们只需要提前确定一个 $\text{d}x$ ，然后二分一个点 $mid$ ，对 $mid - \text{d}x,mid + \text{d}x$ 都求值，然后比较两个值的差。如果一大一小则找到了解，否则比较差的大小缩短边界，由零点存在定理，这样做是对的。又因为单峰或单谷函数的导数有单调性，所以是对的。

Thanks for reading!

2024 11月 20 周三

611 字 · 3 分钟

算法学习笔记 OI 基础算法大数学照亮世界