C++ lower_bound/upper_bound用法解析

1. 作用

lower_bound和upper_bound都是C++的STL库中的函数,作用差不多,lower_bound所返回的是第一个大于或等于目标元素的元素地址,而upper_bound则是返回第一个大于目标元素的元素地址。

从定义就可以看出两者的差别只差在是否取等的的地方 那何必要设置两个函数呢(bushi

2.使用条件

用lower_bound/upper_bound进行二分查找时必须保证查找区间为升序序列!

什么是升序序列?你小学老师没教过你吗(bushi 举个例子你就明白了:

C++ lower_bound/upper_bound用法解析

从第一个元素开始,后面的每一个元素都会大于等于前面一个元素

显然造成这种限制的原因就是出现在制作STL库的人身上 Orz,因为他所写的比较器是‘<’。

3.用法

lower_bound和upper_bound的用法与sort类似:

1 lower_bound(起始位置first,结束位置last,目标元素val);
2 upper_bound(起始位置first,结束位置last,目标元素val);
3  //lower_bound/upperbound的返回值是一个地址值,若要得到目标元素的下标,直接减去数组首地址的值即可

根据C++STL的尿性,同理可得,在lower_bound和upper_bound中我们同样可以添加cmp来进行自定义比较:

1 lower_bound(a,a+n,2,cmp);
2 upper_bound(a,a+n,2,cmp);

当然你在使用lower_bound/upper_bound时要注意其二分查找的区间:

以上面的例子为例,他们的区间都是 [a,a+n)

不要问我[)是什么,这不是小学二年级教的吗(doge,‘[’ 就是大于等于的意思,‘)’ 就是小于的意思,请举一反三。

有人可能会说了,lower_bound和upper_bound只能查找升序序列岂不是很废?那你一定是没有好好学sort ,显然,我们可以通过自定义比较函数来实现降序序列的查找:

1 bool cmp(const int& a,const int& b){
2     return a>b;
3 }
4 lower_bound(a,a+n,val,cmp);
5 upper_bound(a,a+n,val,cmp);

或者你可以更简单一些:

lower_bound(a,a+n,val,greater<int>());
upper_bound(a,a+n,val,greater<int>());

最后,如果函数并没有找到目标元素,则会返回last的地址,且last的地址是越界的。

4.思考

https://www.luogu.com.cn/problem/P2249
原文链接: https://www.cnblogs.com/reasa/p/16638860.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/5724

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月4日 下午7:48
下一篇 2023年2月4日 下午7:49

相关推荐