当前位置:网站首页>图解lower_bound&upper_bound
图解lower_bound&upper_bound
2022-07-31 02:25:00 【桃溪小小生】
两个算法的官方解释
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
lower_bound用于找出升序序列中第一个不小于value的位置, 即找出第一个>=value的位置。
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
upper_bound用于找出升序序列中第一个大于value的位置。
直接从字面理解,稍微有点绕,让我们看两个例子。
元素在列表中存在
对于序列1 2 2 3 3 4 4 5 5 6 6 7
我们对value=3进行lower_bound和upper_bound的调用。
因为lower_bound要求第一个>=,所以图中 [ 标记的位置就是目标位置
因为upper_bound要求第一个>, 所以图中 ) 标记的位置就是目标位置。
- 元素在列表中不存在
对于序列1 3 3 6 6 9 9
我们对value=4进行lower_bound和upper_bound的调用。
因为lower_bound要求第一个>=,所以图中 [ 标记的位置就是目标位置
因为upper_bound要求第一个>, 所以图中 ) 标记的位置就是目标位置。
由此可以看出,如果lower_bound的返回值等于value,说明value在列表中存在,否则就不存在。这也是一种列表中查找元素的方法。
这样一看,lower_bound和upper_bound的起名就很好理解了,“下边界和上边界”,下边界是闭区间,上边界是开区间,组成了左闭右开的区间[ )
这个设计和STL迭代器遵守的左闭右开原则是一致的,所有的begin都包括目标元素,所以的end都不包括目标元素。
我们知道,stl中还有一个常用的查找函数find,都能用于查找元素,两个函数的区别是什么呢?
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
InputIt find( InputIt first, InputIt last, const T& value );
相似点:都接受首尾迭代器和目标元素。
不一样的地方:
- find不要求元素有序,lower_bound要求有序。
- find内部采用==比较元素,lower_bound采用<比较元素。这也是为什么lower_bound要求元素必须是排序好的原因。
- find是线性查找,lower_bound是二分查找。
由此可见,find更通用一些,而lower_bound在有序序列中,查找更加高效。
边栏推荐
- What are the project management tools like MS Project
- Live Preview | KDD2022 Doctoral Dissertation Award Champion and Runner-up Dialogue
- 静态路由+PAT+静态NAT(讲解+实验)
- Installation, start and stop of redis7 under Linux
- StringJoiner详解
- vlan间路由+静态路由+NAT(PAT+静态NAT)综合实验
- Brute Force/Adjacency List Breadth First Directed Weighted Graph Undirected Weighted Graph
- Gateway routing configuration
- FPGA-based vending machine
- Problems that need to be solved by the tcp framework
猜你喜欢
随机推荐
f.grid_sample
经典链表OJ强训题——快慢双指针高效解法
FPGA-based vending machine
力扣刷题之有效的正方形(每日一题7/29)
Observer mode (1)
【AcWing 62nd Weekly Game】
CV-Model [3]: MobileNet v2
全流程调度——MySQL与Sqoop
STP选举(步骤+案列)详解
汉诺塔问题
leetcode-1161: Maximum in-layer element sum
19. Support Vector Machines - Intuitive Understanding of Optimization Objectives and Large Spacing
cudaMemcpy study notes
Manchester City confuses fans with smart scarf that detects emotions
leetcode-128: longest continuous sequence
What does a software test report contain?
mysql index
直播预告 | KDD2022博士论文奖冠亚军对话
AI中的数学思想
What level of software testing does it take to get a 9K job?