lower_bound 函数用法及应用领域和案例分享
lower_bound
是 C++ 标准库
<algorithm>
中提供的一个函数,用于在已排序的序列中
查找第一个不小于给定值的元素的迭代器位置。这个函数经常与
upper_bound
一起使用,
后者用于查找第一个大于给定值的元素的迭代器位置。这两个函数通常用于实现二分查
找算法。
函数原型
cpp 复制代码
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T&
value);
first 和 last 是指向已排序序列的迭代器。
value
是要查找的值。
用法
lower_bound 返回一个迭代器,指向序列中第一个不小于 value 的元素。如果序列中所
有元素都小于 value,则返回 last。
应用领域
1. 二分查找:这是
lower_bound
最常见的应用场景。在已排序的数组中,使
用
lower_bound
可以快速找到某个值或最接近的值。
2. 数据结构:lower_bound 和 upper_bound 常用于实现关联容器(如 set、multiset、
map 和 multimap),这些容器内部都是排序的。
3. 插入操作:当需要在已排序的容器中插入一个元素时,
lower_bound
可以用来找
到插入位置,确保容器仍然保持排序。
案例分享
假设我们有一个已排序的整数数组,并且我们想要找到第一个不小于某个给定值的元素
的位置。
cpp
复制代码
#include <iostream>
#include <algorithm>
#include <vector>