二分法

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

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
2
3
4
5
6
7
8
9
10
11
12

int a[] = {...} // a 中元素有单调性
int l = 1,r = n;
while(l < r)
{
    //int mid = (l + r) / 2;
    int mid = l + (r - l) >> 1; //等价，但更快 & 防溢出
    if(a[mid] <= x)
        l = mid;
    else
        r = mid;
}
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$。

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