C++ STL中的 lower_bound() 和 upper_bound()

àì夳堔傛蜴生んèń 2022-10-23 04:51 96阅读 0赞

##     ##

## 函数作用 ##

iterator lower\_bound( const key\_type &key ): 返回一个迭代器，指向**键值>= key**的第一个元素。

iterator upper\_bound( const key\_type &key ):返回一个迭代器，指向**键值> key**的第一个元素。

[http://blog.csdn.net/niushuai666/article/details/6734403][http_blog.csdn.net_niushuai666_article_details_6734403]

函数lower\_bound()在first和last中的**前闭后开**区间进行二分查找，返回大于或等于val的**第一个元素**位置。如果所有元素都小于val，则返回**last**的位置

举例如下：（有序数组）

一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

则

pos = lower\_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。

pos = lower\_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。

pos = lower\_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。

所以，要记住：函数lower\_bound()在first和last中的**前闭后开**区间进行二分查找，返回大于或等于val的**第一个元素**位置。如果所有元素都小于val，则返回**last**的位置，且last的位置是越界的！！~

返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置

int a\[10\];

int \*t = lower\_bound(a,a+n,key) ; //在数组a中查找key

int post = t-a; // t-a 代表key所在下标

[http_blog.csdn.net_niushuai666_article_details_6734403]: http://blog.csdn.net/niushuai666/article/details/6734403

发表评论取消回复

表情：

评论列表（有 0 条评论，96人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++中的STL：一些常用的STL容器和算法

文章目录对组（Pair）向量（Vectors）列表（Lists）栈（Stack）队列（Queue）集合（Sets）

本是古典何须时尚/ 2023年10月13日 14:36/ 0 赞/ 59 阅读

相关 stl:queue 源码_C ++ STL中的queue :: empty（）和queue :: size（）

stl:queue 源码 In C++ STL, Queue is a type of container that follows FIFO (First-in-First

迈不过友情╰/ 2023年03月05日 12:58/ 0 赞/ 28 阅读

相关 c++ stl stack_C ++ STL中的stack :: empty（）函数

c++ stl stack Prototype: 原型： stack<T> st; //declaration st.empty(); Par

骑猪看日落/ 2023年03月05日 12:50/ 0 赞/ 31 阅读

相关 c++中stl 哈希函数_C ++ STL中的set :: emplace（）函数

c++中stl 哈希函数 C ++ STL set :: emplace()函数 (C++ STL set::emplace() function) set::empl

今天药忘吃喽~/ 2023年03月05日 12:48/ 0 赞/ 31 阅读

相关 c++中stl 哈希函数_C ++ STL中的set :: size（）函数

c++中stl 哈希函数 C ++ STL set :: size()函数 (C++ STL set::size() function) set::size() fun

末蓝、/ 2023年03月05日 12:38/ 0 赞/ 36 阅读

相关 C++ STL中的 lower_bound() 和 upper_bound()

函数作用　　iterator lower\_bound( const key\_type &key ): 返回一个迭代器，指向键值>= key的第一个元素

àì夳堔傛蜴生んèń/ 2022年10月23日 04:51/ 0 赞/ 97 阅读

相关 C/C++中的STL函数库

STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何

灰太狼/ 2022年08月07日 09:40/ 0 赞/ 178 阅读

相关 Java实现lowerBound及upperBound

Java中已经实现了BinarySearch，但没有lowerBound和upperBound，整理一下其实现原理。折半查找中，寻求中间元素的下标时，使用的是“ int

拼搏现实的明天。/ 2022年07月28日 04:25/ 0 赞/ 145 阅读

相关 C++stl中的双向队列

deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素，deque在接口上和vector非常相似，![0_1320717883Pm54.gif][]

ゝ一世哀愁。/ 2022年05月18日 06:15/ 0 赞/ 269 阅读

相关 C++中的STL中map

使用map得包含map类所在的头文件 \include <map> //注意，STL头文件没有扩展名.h map对象是模板类，需要关键字和存储对象两个模板参数：

女爷i/ 2022年01月06日 00:11/ 0 赞/ 358 阅读