整数二分步骤:

  1. 找一个区间[L, R],使得答案一定在该区间中
  2. 找一个判断条件,使得该判断条件具有二段性,并且答案一定是该二段行的分界点
  3. 分析中点Mid在该判断条件下是否成立,如果成立,考虑答案在哪个区间;如果不成立,考虑答案在那个区间
  4. 如果更新方式写的是R = Mid,则不用做任何处理;如果更新方式写的是L = Mid,则需要计算Mid时加上1

分析

二分模板一共有两个,分别适用于不同情况。
算法思路:假设目标值在闭区间[l, r]中, 每次将区间长度缩小一半,当l = r时,我们就找到了目标值。

二分查找的ans分为一下两种:

  1. ans在红色区间右端点
  2. ans在绿色区间左端点

版本1:ans是绿色区间(后半段)的左端点

当我们将区间[l, r]划分成[l, mid][mid + 1, r]时,其更新操作是r = mid或者l = mid + 1,计算mid时不需要加1。

c++代码模板:

check(mid)返回值:

  • true:mid在绿色区域
  • false:mid不在绿色区域
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2:ans是红色区间(前半段)右端点

当我们将区间[l, r]划分成[l, mid - 1][mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。

c++代码模板:

check(mid)返回值:

  • true:mid在红色区域
  • false:mid不在红色区域
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;
}

为什么需要+1
原因是如果不加上1,那么mid得到的是下取整的数,那么有可能[m,r]更新过后m会一直等于mm+1==r的情况)会陷入死循环。

对于存在多个重复数,模板一是查找左边界,模板二是查找右边界。

原理就是这两种情况就是一个是从小到大找,一个是从大到小找。因为二分的前提是要有序嘛~嘿嘿嘿

最后修改:2022 年 02 月 06 日
如果觉得我的文章对你有用,请随意赞赏