我们说过搜索，如果目标函数f(x)是单调的，那就可以尝试二分。

登录以参加训练计划

我们说过搜索，如果目标函数f(x)是单调的，那就可以尝试二分。

单调的

如果说假定有一个函数 （ 或者有一个数组 ），满足对于所有的$L ≤ x_1 < x_2 ≤ R$，必然有 $f(x_1) < f(x_2)$ ( 数组的话是 $f[x_1] < f[x_2]$) 那么我们就说着个函数 / 数组是单调的。

单调分单调递增和单调递减。

说人话就是，从左到右，里面的元素一个比一个大（或者不比前面小），我们就可以利用二分去进行搜索。

==显然，对于一个升序排列，既然$x_i$已经大于$target$了，对于任意$x_j, (j > i)$，必然有$x_j > target$。

不要管上面的

云里雾里的定义说不通不要紧，看下面这个数组，思考如下问题：

a = [1,3,5,7,8,9,54,634,65536,87878]

1. 找一下634在不在里面
2. 5在的话在第几位？
3. 有多少个数比6291大？
4. 第k个数是啥？ （对于数组当然这个排好序访问下标就可以了，但对于函数就不一定能这样了）

这些问题都可以转成，二分。

在单调的空间上进行搜索

还有一种搜索给出了答案的明确范围，并且我们知道$f(x)在该范围内是单调的。利用二分查询的思路，我们也可以取得O(logn)级别的搜索算法。

二分的一些麻烦

1. 收敛到上下区间
2. 二分搜索空间的构造