刷题

二分查找算法模板

nkul · 10月1日 · 2020年 · 127次已读

原文《二分查找算法模板-AcWing》

https://www.acwing.com/blog/content/31/

假设目标值在[l ,r]中,现使用二分法查找,当l = r时,找到目标值!

模板有两种!

模板一

将区间分为[l , mid],[mid + 1 , r ],此时 mid = l + r >> 1;

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;
}

模板二

将区间分为[l , mid – 1],[mid , r ],此时 mid = l + r + 1 >> 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;
}

当然,以上两种模板的返回值,不一定为l,具体返回值视 check函数而定!一般等号在哪里,返回值就是哪个!

简单的记法:若l = mid 没有加1,则mid初始值加1!



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!