• 热门专题

C++中lower_bound函数和upper_bound函数

作者:  发布日期:2014-04-09 18:37:29
Tag标签:函数  
  • STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间(当然这也是运用二分查找的前提),下面记录一下这两个函数。

    ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

    ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。

    lower_bound和upper_bound如下图所示:

    1.lower_bound函数源代码:

    //这个算法中,first是最终要返回的位置
    int lower_bound(int *array, int size, int key)
    {
        int first = 0, middle;
        int half, len;
        len = size;
    
        while(len > 0) {
            half = len >> 1;
            middle = first + half;
            if(array[middle] < key) {     
                first = middle + 1;          
                len = len-half-1;       //在右边子序列中查找
            }
            else
                len = half;            //在左边子序列(包含middle)中查找
        }
        return first;
    }

    2.upper_bound函数源代码:

    int upper_bound(int *array, int size, int key)
    {
        int len = size-1;
        int half, middle;
    
        while(len > 0){
            half = len >> 1;
            middle = first + half;
            if(array[middle] > key)     //中位数大于key,在包含last的左半边序列中查找。
                len = half;
            else{
                first = middle + 1;    //中位数小于等于key,在右半边序列中查找。
                len = len - half - 1;
            }
        }
        return first;
    }


About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规