文档章节

lower_bound 和upper_bound

清风伴月
 清风伴月
发布于 2017/05/06 23:28
字数 233
阅读 13
收藏 0

STL lower_bound 和upper_bound

     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

stl 源码:

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

stl 源码:

int upper_bound(int *array, int size, int key)
{
    int first = 0, 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;
}

 

© 著作权归作者所有

上一篇: C++内存管理
下一篇: c++ unique函数
清风伴月
粉丝 1
博文 129
码字总数 255659
作品 0
海淀
程序员
私信 提问
python实现lower_bound和upper_bound

由于对于二分法一直都不是很熟悉,这里就用C++中的lowerbound和upperbound练练手。这里用python实现 lowerbound和upperbound本质上用的就是二分法,lowerbound查找有序数组的第一个小于等于目...

mambakb
2018/11/29
0
0
STL lower_bound和upper_bound算法

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

吃一堑消化不良
2016/09/06
58
0
小朋友学C++(46): lower_bound()和upper_bound()

lowerbound( )和upperbound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。 在从小到大的排序数组中, lowerbound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个...

海天一树X
02/05
0
0
[LeetCode] Count of Range Sum 区间和计数

Given an integer array , return the number of range sums that lie in inclusive. Range sum is defined as the sum of the elements in between indices and ( ≤ ), inclusive. Note: ......

机器的心脏
2017/12/15
0
0
Class SafeArray

Class SafeArray public final class SafeArray{ // Constructors public SafeArray(int vt); public SafeArray(int vt, int celems); public SafeArray(int vt, int celems1, int celems2);......

小青_1989
2014/06/06
36
1

没有更多内容

加载失败,请刷新页面

加载更多

Flink Graph生成及Hash生成分析

222

MrPei
6分钟前
1
0
[译]Android Activity 和 Fragment 状态保存与恢复的最佳实践

https://blog.csdn.net/growing_tree/article/details/53759564 https://blog.csdn.net/u013588712/article/details/54691791...

shzwork
7分钟前
1
0
调用第三方快递鸟物流单号查询接口API代码示例

最近进行网站后台开发,需要实现物流的即时查询,发现之前集成的 快递100物流查询 API ——【PHP 快递查询源码资源】 已经不能正常使用了; 为了方便以后的业务需求,经过比较,最后选择使用...

程序的小猿
14分钟前
2
0
java Poi 操作执行excel 文件中函数问题

poi 读取excel 文件,当excel 有函数时,poi直接读取返回的是excel 函数,并不能返回函数计算结果: 解决步骤: sheet.setForceFormulaRecalculation(true); 判断该列格式是否为...

早a
22分钟前
3
0
js模拟实现输入框input事件

直接修改value值是无法触发对应元素的事件的。 通过发送输入框input事件了, 可以触发。 这里简单封装了一个方法. window.inputValue = function (dom, st) { var evt = new InputEvent('i...

開援带碼
23分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部