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

二分的一点点理解

作者: 作者的头像   fromthetop ,  2020-01-25 16:26:57 ,  所有人可见 ,  阅读 635


1



//一句话:mid和+1  只能留一个!

当区间[l,r]的更新是r=mid;l=mid+1是,计算mid是不需要加1
也就是说mid要放在下次检查中时,就不用在二分的时候加1
同理,如果二分的时候mid不要了,就要+1
int bsearch(){
 while(l<r)
 {
   int mid=l+r>>1;
   if(check(mid)) r=mid;  //mid通过check,并且还要接受下次check 
   else l=mid+1;
 }
}
总结就是写成r=mid 不加1
写成l=mid 就要+1


0 评论

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

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