设为首页 加入收藏

TOP

二分
2023-07-23 13:39:12 】 浏览:95
Tags:二分

1.整数二分

用一个性质将区间分为满足性质和不满足性质,答案是二分的边界

情况一

代码分析
int bsearch_1(int l,int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; //如果mid满足性质缩小区间为[l,mid]
        else l = mid + 1; //如果mid不满足性质缩小区间为[mid+1,r]
    }
    return l;
}
//最后输出l或r都行,因为二者相等

如果[l,r]中没有ans那么返回的是大于ans的第一个数

情况二

代码分析
int bsearch_2(int l,int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid; //如果mid满足性质缩小区间为[mid,r]
        else r = mid - 1; //mid不满足性质缩小区间为[l,mid-1]
    }
    return l;
}

如果[l,r]中没有ans那么返回的是小于ans的第一个数

2.浮点数二分

例:输出x的平方根,x可能为小数

代码分析
#include<iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = x; //左右端点
    while (r - l > 1e-8) //l与r的距离小于等于1r-8退出循环
    {
        double mid = (l + r) / 2; //注意浮点数没有位运算
        if (mid * mid >= x) r = mid; //mid在答案的左边缩小区间为[l,mid]
        else l = mid; //在答案右边缩小区间为[mid,r]
    }

    cout << l; //输出l或r都行,二者相等
    return 0;
}

知识点

精度:精度eps至少需要比保留位数多2位

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇lambda表达式基础 下一篇P1352 没有上司的舞会+P1122 最大..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目