二分法求 有序序列第一个满足某个条件的元素的位置的方法(模版):
//二分区间为左闭右闭[left, right],初始值left、right必须覆盖解的所有可能 int solve(int left, int right){ int mid; while(left < right){ //对于[left,right]来说, left == right意味着找到了解 mid = (left + right) / 2; if(条件成立){ //条件成立,第一个满足条件的元素的位置 <= mid right = mid; //往左子区间[left, mid]查找 } else { left = mid + 1; //往右子区间[mid + 1, right]查找 } } }
应用一:求第一个大于某个值x的元素的位置
int upper_bound(int A[], int left, int right, int x){ int mid; while(left < right){ mid = (left + right) / 2; if(A[mid] > x){ right = mid; }else{ left = mid + 1; } } return left; }
应用二:求第一个大于等于某个值x的元素的位置
将判断条件 > 改为 >= 即可
数有序列中有多个相同的元素 :寻找第一个大于等于x的元素的位置L和第一个大于x的元素的位置R , 则 [L,R) 内的元素都等于x
🔗C++二分查找_shldy1999的博客-CSDN博客_c++二分查找仅供参考,优先选择上面的方法,不需要考虑死循环等问题。
原文地址:http://www.cnblogs.com/yccy/p/16838537.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性