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

二分查找模板学习笔记

作者: 作者的头像   自律给你自由 ,  2019-07-15 12:55:54 ,  所有人可见 ,  阅读 2762


7


11

参考闫学灿大佬视频讲解和模板:
https://www.acwing.com/blog/content/31/

二分模板

算法思路:假设目标值在闭区间[l, r]中,每次将区间长度缩小一半,当l = r 时,就找到了目标值。
屏幕快照 2019-07-15 上午10.11.49.png

模板一

mid = l + r >> 1, (下取整)
if mid是绿色,分界点target在mid左侧,可能包括mid, [l,r]->[l,mid], r = mid
else mid是红色,分界点target在mid右侧,不包括mid , [l,r]->[mid+1,r], l = mid + 1

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

C++代码模板:

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

屏幕快照 2019-07-15 上午10.11.56.png

模板二

mid = l + r +1 >> 1,(上取整)
if mid 是红色,分界点target在mid 右侧,可能包括mid, [l,r]->[mid,r], l = mid
else mid 是绿色, 分界点target在mid 左侧, 不包括mid, [l,r]->[l,mid - 1] r = mid - 1

注意:
如果模板二用mid = l + r >> 1,(下取整)
当l = r - 1, mid = l + r >>1 == 2l + 1 >>1  ==  l
if mid 是红色,[l,r]->[mid,r]  ->[l,r],死循环。

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

C++代码模板:

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 评论


用户头像
0x3F3F3F3F3F3F3F3F   2021-12-05 15:40         踩      回复

感谢分享


用户头像
Max   2019-07-16 11:53         踩      回复

感謝分享 👍


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

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