C++ lower_bound/upper_bound用法解析
1. 作用
lower_bound和upper_bound都是C++的STL库中的函数,作用差不多,lower_bound所返回的是第一个大于或等于目标元素的元素地址,而upper_bound则是返回第一个大于目标元素的元素地址。
从定义就可以看出两者的差别只差在是否取等的的地方 那何必要设置两个函数呢(bushi
2.使用条件
用lower_bound/upper_bound进行二分查找时必须保证查找区间为升序序列!
什么是升序序列?你小学老师没教过你吗(bushi 举个例子你就明白了:
从第一个元素开始,后面的每一个元素都会大于等于前面一个元素
显然造成这种限制的原因就是出现在制作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
最新文章
- Visual Studio 版本转换工具WPF版开源了
- dom4j使用总结
- vmware备忘
- 学习JavaScript闭包
- codis集群安装
- Excel 导入 Sql Server出错——“文本被截断,或者一个或多个字符在目标代码页中没有匹配项”错误的解决
- 采集数据和memchche的存储使用,分页展示
- ThinkPHP函数详解:session方法
- mysql C API 字符串玩转备份调优
- RabbitMQ(从安装到使用)
- 浅谈prototype和__proto__
- js-txt文本处理
- 【learning】多项式相关(求逆、开根、除法、取模)
- 招商信诺生产jvm 配置和自己的eclipse jdk配置
- Java中Map和Object的互相转换方式
- JS第三部分--BOM浏览器对象模型
- servlet-response学习笔记
- C/C++预处理器
- Access restriction: The constructor SunJCE() is not accessible 错误
- Inondb中的checkpoint
热门文章
- Apache DolphinScheduler&;ShenYu(Incubating) 联合 Meetup,暖春 3 月与你相约!
- 喜讯:“行走的文档” 当选 Apache DolphinScheduler Committer啦
- 使用dotnet-monitor分析在Kubernetes的应用程序:Sidecar模式
- PerfView专题 (第九篇):洞察 C# 中的 LOH 内存碎片化
- 网安等保-Linux服务器之最新Ubuntu-22.04-LTS系统内核优化与安全加固配置脚本使用分享
- java数组---数组的使用(打印,求和,最大值)
- vs完整编译Opencv+contrib
- 集成 Redis &; 异步任务 - SpringBoot 2.7 .2实战基础
- KingbaseES interval 分区表介绍
- go 中解析JSON的三种姿势