AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

二分法小结

作者: 作者的头像   water-lover ,  2020-02-05 18:44:22 ,  所有人可见 ,  阅读 1673


9


9

二分法小结:

思想:
在一个区间进行二分,每次都要选择答案所在的区间进行处理,亦即每次的区间都会把答案覆盖掉,每一次都能保证我们的
区间有答案。二分的时候我们一定会保证这个区间是有答案的,那么当区间长度是1时,这个区间里的数就是答案。

二分和单调性的关系:
有单调性的一定可以二分,但可以二分的不一定有单调性,即没有单调性也可以二分。

二分和题解的关系:
我们二分的时候一定是有解的。如果是无解,和题目是有关的,而与二分模板无关。
无解并不是在二分中是无解,而是我们二分完后通过这个性质可以判断出原问题无解。因此,二分时不必考虑无解情况,无
解一定是与题目有关的,我们可以根据二分出来后的边界来判断题目是否有解。

1.整数二分 ----需要考虑边界问题

整数二分解题步骤:
1.找到一个区间[l, r], 使得答案一定在区间中。
2.找到一个判断条件,使得判断条件具有二段性,并且答案一定是该二段性的分界点。
3.分析中点mid在该判断条件下是否成立。
  如果成立,考虑答案在哪个区间;
  如果不成立,考虑答案在哪个区间。
4.如果更新方式是 r = mid,则mid = l + r >> 1;
  如果更新方式是 l = mid, 则mid = l + r + 1 >> 1。
  (或理解为:当分段点右侧满足性质时,r = mid, mid = l + r >> 1;
            当分段点左侧满足性质时,l = mid, mid = l + r + 1 >> 1.)
  ```
  当l = mid时,mid = l + r + 1 >> 1 . 原因分析如下:
  当区间长度为1时,即当l = r - 1 时,mid = l + r >> l = l, mid = l + r + 1 >> l = r.
  假设此时更新方式是 l = mid.如果此时恰好满足性质,则l会更新为mid, 即l = mid = l + r >> l = l,出现了死循环。
  所以为了避免l再次更新依然为其自身,则让mid向上取整,即 mid = l + r + 1 >> 1.此时l = mid = r,不会出现死循环。
  ```

整数二分算法模板 —— 模板题 AcWing 789. 数的范围 -----题目及题解链接AcWing

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
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;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
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;
}

2.浮点数二分 ----无需考虑边界问题

浮点数二分解题步骤:
1.找到一个区间[l, r], 使得答案一定在区间中。
2.找到一个判断条件,使得判断条件具有二段性,并且答案一定是该二段性的分界点。
3.分析中点mid = (l + r) / 2 在该判断条件下是否成立。
  如果成立,考虑答案在哪个区间;
  如果不成立,考虑答案在哪个区间。
4.确定更新方式r = mid 或 l = mid。

浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根-----题目及题解链接AcWing

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

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

附:关于浮点数二分中区间精度的选取: ----来自y总的经验之谈

一般来说区间精度为1e-6就很高了。如果题目让结果保留4位小数,那么精度可以取1e-6,;如果题目让结果保留5位小数,那
么区间精度可以取1e-7.以此类推···简言之,区间精度至少要比题目要保留的小数位数高2位。

模板来源:AcWing

1 评论


用户头像
马老师糖尿病害我蛀牙   2024-02-28 17:39         踩      回复

tql


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息