算法导论——二分

二分是一种**极其简单并且常见的算法**，它的目的是为了**在有序的数列中快速找到符合某个条件的最大或最小值**（注意：必须有序） 为什么说是**快速**呢？因为二分的 **时间复杂度是$O \left ( \log_2 n \right )$，而顺序查找则是$O \left ( \dfrac{n}{2} \right )$**，所以，二分显然快于顺序查找。（注：这是在$check$函数为$O \left ( 1 \right )$的情况下） 二分写法**多的要死**，这里只写一种： ```cpp while(l<r) { m=(l+r)/2; if(check(m))l=m+1; else r=m; } ``` （注：l为左边界，r为右边界，m为中间，check依据题目而定） 二分有两大类：**二分查找、二分答案** 二分查找是指**用二分查找一个下标**，二分答案则是**用二分查找一个值**，这是两者的区别 一般来说，**第二种**，也就是二分答案用的要多一些，但是**在导弹拦截中用的是二分查找** [这题](https://www.luogu.org/problemnew/show/P2855)就是一道经典的二分答案题，重点就在check函数上 二分最难的并不是背板子，而是**写出正确的、复杂度低的check函数** 虽然二分的复杂度最多是$O \left ( 32*f \left ( check \right ) \right )$，但是如果**check函数复杂度过大**，那么，二分也无能为力 二分是一种简单而又好用的算法，但是请注意：**前提条件是有序！！！**