首页 / 更多教程 / 二分使用条件 + 代码模板
二分使用条件 + 代码模板
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二分使用条件 + 代码模板,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含875字,纯文字阅读大概需要2分钟。
内容图文
![二分使用条件 + 代码模板](/upload/InfoBanner/zyjiaocheng/1027/1b4b4437f6ab4da795c50fc84d7ff789.jpg)
1.答案有确定的范围(时间复杂度一般近似O[lg(right-left+1)];
2. 问题的答案是单调的
注意: check验证函数的编写是二分答案的核心。出不出错就看它了
查找值的时候, 记得中间等于号的使用:
理解至上:
当mid = l + r + 1 , 取到的值是偏右的, l没有问题, 后面r = 得偏回来, 不满足条件就不加这个边界, r = mid - 1
当mid = l + r , 取到的值是偏左的, r没有问题, 后面l = 得偏回来, 不满足条件就不加这个边界, l = mid + 1
//比如:
mid = l + r + 1>> 1; if(mid >= n) l = mid;
else r = mid - 1;
//----------------------
mid = l + r >> 1; if(mid >= n) r = mid; else l = mid + 1;
模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质 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; }
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; }
内容总结
以上是互联网集市为您收集整理的二分使用条件 + 代码模板全部内容,希望文章能够帮你解决二分使用条件 + 代码模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。