#AcWing系列课程Level-2笔记——3. 整数二分算法

佚名 6年前 (2020-02-12) 算法 812人围观抢沙发百度已收录

整数二分算法

编写整数二分，记住下面的思路，代码也就游刃有余了！

1.首先找到数组的中间值，mid=(left+right)>>1，区间[left, right]被划分成[left, mid]和[mid + 1, right]；如果是mid = l + r + 1 >> 1，区间[left, right]被划分成[left, mid - 1]和[mid, right]。

2.然后通过check(mid)判断中间值是不是满足这个性质,check是根据不同的题型编写的。

3.最后就能使用折半，缩小区间了，如果区间缩到了1，那么那个也就是答案。

整数二分算法的核心

二分的本质不是单调性

如果有单调性，一定可以二分，但是可以二分的题目，不一定有单调性。

二分的本质，问题一半满足，一半不满足，可以寻找到边界，这个边界可以将数组分为两个部分。因为整数边界必须做出选择，代码将有两个模板。而浮点数不是。

二分的主要思想是折半

二分一定是有解的，那个边界可以二分出来，但题目可能是无解的。

整数二分算法的代码模板

添加了注释

bool check(int x) {/* ... */} //检查x是否满足某种性质

// 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;//左边，check()判断mid是否满足性质
        else l = mid + 1;//右边
    }
    return l;
}
// 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) r = mid-1;//左边
        else l = mid;//右边
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/problem/content/791/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。