算法总结之二分

2021.7.16更新：二分只针对于一个对象进行查找！

今天要讲二分！二分是一个效率非常高的算法，可以与dp等许多算法结合以优化时间复杂度（先正经一下）。

一、定义（指我印象里的）

在一个单调序列里，将需要查找的关键字与序列中间位置的关键字相比较，不断分割查找范围，直到找到答案。

注意，序列一定要是单调的！！！

二、分类

二分主要包含整数二分、实数二分（浮点数二分）、二分答案。

　　1.整数二分

通过找到满足当前条件的左或右区间，使数组一分为二，直到找到边界点，即答案

代码实现

int bsearch_2(int l, int r) {
      while(l < r) {
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
      }
      return l;
}

int bsearch_2(int l, int r) {
      while(l < r) {
            int mid = l + r + 1 >> 1;
            if(check(mid)) r = mid;
            else  = mid - 1;
      }
      return l;
}

经典例题：P1571 眼红的Medusa

　　2.实数二分

和整数二分不同，浮点数不存在由于取整导致的边界问题，每次二分区间严格减半，因此比整数二分简单的多，每次更新边界时直接让r = mid或l = mid即可。（原谅我的语文不好，这话我确实说不明白，所以摘了知乎上的一句话，原po在这）
代码实现

int search（int l，int r)
{
     while(r - l > 所给精度) {
        double mid = (l + r) / 2;
        if(f(mid)>关键字) 
        {
            r = mid;              
        } 
        else
        {
            l = mid;
        }
    }
}

经典例题：P1024 [NOIP2001 提高组] 一元三次方程求解

　　3.二分答案

二分答案求解特征

(1)求最大/最小值;

(2)答案离散(答案有有限种可能);

(3)容易判断答案是否正确。
二分答案题的做法即是:

(1)确定答案区间;

(2)在保证答案在区间内的前提下,逐步缩小区间;

(3)当区间缩小到仅包含一个可能解时，该可能解即为答案。（这段也是摘的，原po)
经典例题：P1873 砍树

好啦，到这这个烂俗彻底的总结就完事了。

再推荐两篇我觉得写的特别好的博客：

https://www.cnblogs.com/lcosmos/p/9438705.html

https://blog.csdn.net/qq_41157137/article/details/84074341