早就想写了。咕了半年，难过。
0x0210 二分查找
0x0211 引入
如同贪心，二分这样的基础算法在生活中也被广泛应用。
众所周知有一个程序员笑话：有人从书店买了一大摞书，经过警报器的时候警报器响了。工作人员要求他依次带着每一本书经过警报器，以此确定是哪本书没有消磁。
结尾不会讲了，总之是这个意思。工作人员这样的操作本质上等价于暴力查找，其复杂度是 $O(n)$ 的。
试想一种更复杂的情况：有 $n$ 本书按书名字典序排序，$q$ 个人依次来买书，那么你还要暴力查找吗？这是 $O(nq)$ 的，兴许客人到最后都等急了。
因此，我们引入了二分查找。事实上，一般这时我们也不会去真的一本一本找。假设客人要买的是《一本通提高篇》，我们可能会随机在这一堆书里抽一个靠中间的，《论玩原神的重要性》。它的首字母是 L，我们要找的是 Y。因此要在这本书之后再去找《一本通提高篇》。这样一直找下去，最终就能更快速地找到想要的书了。
小声：为什么不用 Trie 树。
0x0212 形式化
给定含 $n$ 个元素、严格单调递增的整数数组 $a_i$，$q$ 次询问，每次询问给定 $x$，输出满足 $a_i=x$ 的 $i$（由于数组严格单调递增，这样的 $i$ 最多只有一个），若不存在这样的 $i$ 则输出 $-1$。
先考虑一次询问。当任意选取一个 $i$ 时，可能发生的有：
- $a_i < x$。既然对于 $i$ 它成立，那么对于一个 $j<i$，一定有 $a_j < a_i < x$，继而所有 $j \leq i$ 都不可能成为答案。
- $a_i > x$。类似地，所有 $j \geq i$ 都不可能成为答案。
- $a_i = x$。$a_i$ 即为答案。
但是 $i$ 要怎样选取呢？设当前可能为答案的区间为 $[l, r]$，第一种情况下，我们可以排除 $i-l+1$ 个元素；第二种情况下，我们可以排除 $r-i+1$ 个元素。为了让我们的算法在任何情况下优秀，要让最坏情况下排除的元素最多。也就是最大化 $\min(i-l+1, r-i+1)$，应取 $i = \frac{l+r}{2}$。$l+r$ 为奇数的情况下，我们不能取小数下标，向下和向上取整都能使其最大化。由于 C++ 的正整数除法默认向下取整，取下整相对容易实现。伪代码如下：
1 | int solve(int n, int a[]) { |
0x0213 加强版
如果数组不再严格单调递增呢？现在，给定的整数数组只保证单调递增，可以有重复的元素。要求的为最小的 $i$ 满足 $a_i=x$。
还是考虑单次询问。但是这次有一些不同。当任意选取一个 $i$ 时，可能发生的有：
- $a_i < x$。既然对于 $i$ 它成立，那么对于一个 $j<i$，一定有 $a_j < a_i < x$，继而所有 $j \leq i$ 都不可能成为答案。
- $a_i \geq x$。我们合并了两种情况。此时，即使 $a_i = x$，$i$ 也可能不是答案（因为可能有更小的 $i$ 也满足）。$i$ 仍有是答案的可能性，但所有 $j > i$ 都不可能成为答案。
同上，设当前可能为答案的区间为 $[l, r]$，第一种情况下，我们可以排除 $i-l+1$ 个元素；第二种情况下，我们可以排除 $r-i$ 个元素（注意这里少了 $1$）。最大化 $\min(i-l+1, r-i)$，应取 $i=\frac{l+r-1}{2}$。在 $(l+r)$ 为奇数时，此值等于 $\lfloor\frac{l+r}{2}\rfloor$；为偶数时，此值为小数，同上地，向上、向下取整都可以最大化。若取上整，则相当于取 $\frac{l+r}{2}$。综上，若取上整，可以将两种情况同时考虑，并不失最优性。
伪代码如下：
1 | int solve(int n, int a[]) { |
0x0214 另一种写法
以下是一种（作者认为的）更好理解的做法。
我们可以定义一个位置为合法解，当且仅当 $a_i \geq x$。我们要选择的，是 $i$ 最小的合法解 $ans$——如果 $a_{ans}=x$，它就是我们需要的答案；否则无解。这很好证明，利用单调性即可。
因此，我们要额外维护一个 $ans = \min i$，为当前见到的最小的“合法解”。
单次询问，选取一个 $i$ 时，可能有：
- $a_i < x$。既然对于 $i$ 它成立，那么对于一个 $j<i$，一定有 $a_j < a_i < x$，继而所有 $j \leq i$ 都不可能成为答案。
- $a_i \geq x$。所有 $j \geq i$ 都是合法解，这一部分中最小的合法解是 $i$；而对一个 $j < i$，$j$ 可能是更小的合法解。因此，我们要再去尝试 $j<i$ 的部分。
利用与 0x0212 相同的方式，我们可以推出此处选择 $i = \lfloor\frac{l+r}{2}\rfloor$ 最优。伪代码如下：
1 | int solve(int n, int a[]) { |
0x021f 补充信息
条件：显然需要单调性。
一般写法：一般来说采用 0x0213 或是 0x0214 中的写法——0x0212 写法的普适性太差了。
时间复杂度：由于每次我们选取的 $i$ 使得区间减半，其复杂度为 $T(n) = T(\frac{n}{2})+1$，推得 $T(n) = O(\log n)$。
一般用途：带修改的多次询问时常使用——不带修改可用 std::sort 替代，单次询问可用暴力替代。
STL：std::lower_bound，其求出的是第一个满足 $a_i \geq x$ 的位置（的指针）。另外还有 std::upper_bound，其求出的是第一个满足 $a_i > x$ 的位置（的指针）（注意这里是 $>$）。事实上，这两个问题相当于什么呢？相当于，若你要将 $x$ 插入数组中，保持数组的单调性，能够插入的第一个位置和最后一个位置。
0x0220 二分答案
0x0221 概念
有些题目中，可能需要求：满足条件 $p(x)$ 的最小（大）的 $x$。朴素的想法是枚举值域内的每一个 $x$，但值域较大时会 TLE。如果满足条件的 $x$ 满足一定条件呢？
有的时候，对于任意一对值域内的数 $x<y$，就会有 $y$ 的限制比 $x$ 更松（也可能反之）。这是什么意思呢？以一道题举例：条件 $p(x)$ 为存在至少 $m$ 个数满足 $a_i \leq x$。那么，对于一个 $x<y$，若 $x$ 满足条件，$y$ 一定满足。
这种情况下，若我们将满足条件写作 $1$，不满足写作 $0$，并将值域内从小到大的每一个 $x$ 对应的 $p(x)$ 写出来，则必然形如 $0\dots 01\dots 1$（或 $1\dots 10\dots 0$）。这是满足非严格单调性的，可以使用二分法找到满足条件的最小（大）的 $x$。
当我们证明（或者猜测）条件具有单调性时，就可以使用二分法求 $x$ 了。
设给定一个 $x$，判定 $p(x)$ 是否为真的时间复杂度是 $O(f)$；$x$ 的值域是 $S$；则二分答案的时间复杂度是 $O(f \log |S|)$。
0x0222 浮点数做法
如果要求出一个精度达到一定要求的实数解呢？此时，如果条件仍然具有单调性，我们可以进行二分。但是，整数二分依赖排除 $[i, r]$ 之后剩下的区间是 $[l, i-1]$（反之亦然）这一特性。浮点数下，剩下的区间是 $[l, i)$，且无法使得区间内仅剩一个可能的值。
由于我们只需要一定的精度，只要区间 $[l, r]$ 的长度 $r-l$ 远小于这个精度，就能够得到满足精度的答案了。这样，我们得以完成二分的操作。
伪代码如下：
1 | bool check(double mid) { |
0x0230 三分法
如果需要求单峰函数的极值点，通常可使用二分法衍生出的三分法求解。
假设 $f(x)$ 为存在且仅存在一个极大值的单峰函数，当前已经确定了其极值点的 $x$ 坐标范围是 $[l, r]$。取两个值 $i, j$ 满足 $l < i < j < r$，可能发生的有：
- $f(i) < f(j)$。若极值点在 $[l, i]$，则函数在 $[i, r]$ 上应为单调递减，与事实不符，因此极值点不在 $[l, i]$ 上。若极值点在 $[i, j]$，显然成立。若极值点在 $[j, r]$，函数在 $[l, j]$ 上应为单调递增，可能成立。综上，可以将区间缩小为 $[i, r]$。
- $f(i) > f(j)$。类似地，可以将区间缩小为 $[l, j]$。
- $f(i) = f(j)$。事实上，若函数（在极值点左/右）非严格单调递增/减，这种情况下我们无法排除任何一段区间。但若函数严格单调递增/减，则可以将区间缩小为 $[i, j]$。为了编码方便，可以将此情况归入上述两种中的任意一种，不影响复杂度。
根据推论，取 $i, j$ 时，需要最大化 $\min(i - l, r - j)$。取 $i = j = \frac{l+r}{2}$ 最优，但此时显然做不到排除。因此对其增加扰动，即取 $i = \frac{l+r}{2} - \varepsilon, j = \frac{l+r}{2} + \varepsilon ~\mathrm{(a)}$，其中 $\varepsilon$ 为一个极小正数（可取 $10^{-6}$ 等）。常见的其它取法还有 $i = \frac{2l+r}{3}, j = \frac{l+2r}{3} ~\mathrm{(b)}$、$i = \frac{l+r}{2}, j = \frac{i+r}{2} = \frac{l+3r}{4} ~\mathrm{(c)}$ 等等。
时间复杂度：设求一次 $f(x)$ 的时间复杂度为 $O(p)$，值域为 $S$；则三分法的时间复杂度是 $O(p n \log_2 |S|)$。
0x0240 例题
0x0243 喷水装置
三分模板，但为了严谨性需要证明若干个单谷二次函数取 $\max$ 后仍为单谷函数。
证明链接：https://blog.csdn.net/mobius_strip/article/details/45618095?utm_source=copy
0x0245 扩散
考虑确定时间时判定 $p(x)$。若两个点能够通过直接扩散连接，它们的曼哈顿距离需要 $\leq 2x$。这之后，我们枚举每一个点对，若它们能够直接连接，则在并查集中将两个点合并。最后，如果所有点在并查集中均被合并，则此 $x$ 合法。
0x0246 灯泡
纯纯垃圾推式子题。作平行线后，可以通过相似求解投影高度。
0x0247 传送带
三分套三分模板题。考虑确定了在第一条传送带上走了多远后，在第二条传送带上走的路程-总的用时形成一个单谷函数，可以三分。再考虑，在第二条传送带永远走最优解时，第一条传送带上走的路程-总的用时也形成一个单谷函数，也可以三分。
这题给了我们一个启发：三分的目标函数可以是通过其他算法动态求出的，而并非是一个给定的函数。
时间复杂度是 $O(\log^2 n)$，$n$ 为值域大小。