二分法求 有序序列第一个满足某个条件的元素的位置的方法(模版):

//二分区间为左闭右闭[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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性