C++中std::upper_bound用法解析

在C++标准模板库（STL）的算法工具箱里，upper_bound() 是一把精准的“探针”。

它的核心任务很明确：在一个已经排好序的区间 [first, last) 内，快速定位第一个严格大于指定值 value 的元素。

该函数会返回指向该元素的迭代器。其高效的二分查找机制，让它成为处理有序数据时的首选工具。

1. 函数的标准语法形式

我们先来看看它的标准签名：

template
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

2. 核心行为与返回值

upper_bound() 的核心行为是：

• 在范围 [first, last) 内，搜索第一个使得“元素值大于 val”成立的位置。
• 返回指向该位置的迭代器，类型与传入的 first、last 一致。
• 如果范围内没有这样的元素，则返回 last（区间的“尾后”迭代器）。

3. 典型应用一：在标准容器中使用

对于 std::vector、std::array 这类顺序容器，结合其自带的 begin() 和 end() 迭代器调用 upper_bound() 非常自然。

由于容器本身有序，这个操作能在 O(log n) 的时间复杂度内完成定位。

马上学习“C++免费学习笔记（深入）”：

#include
#include
#include
using namespace std;
int main() {
vector v = {1, 2, 3, 4, 5};
// 查找第一个大于3的元素
auto it = upper_bound(v.begin(), v.end(), 3);
if (it != v.end()) {
cout << *it << endl; // 输出：4
}
return 0;
}

如果想查找 vector 中首个大于数值 3 的元素的下标（索引），可以这样操作：

int idx = upper_bound(v.begin(), v.end(), 3) - v.begin();
cout << idx << endl; // 输出：3

输出结果为 3，对应值为 4 的元素在 vector 中的位置，符合“第一个大于3”的预期。

4. 典型应用二：在普通数组中使用

对普通数组执行相同的查找操作，原理相通，只是传递的迭代器变成了指针。

#include
#include
using namespace std;
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
// 查找第一个大于25的元素
int* p = upper_bound(arr, arr + n, 25);
if (p != arr + n) {
cout << *p << endl; // 输出：30
}
return 0;
}

最终输出值为 30，因为它是数组中第一个大于 25 的数。

upper_bound() 同样支持对数组的任意子区间进行精准查找。

一个非常常用的表达式是：int pos = upper_bound(a + l, a + r, m) - a;

这条语句的用途是：获取数组 a 中，在子区间 [l, r) 内第一个大于 m 的元素，其在整个数组中的位置索引。

这里，a 代表数组的起始地址（指针），l 与 r 则分别限定了查找区间的左闭右开边界。

这种写法在算法竞赛和需要处理局部数据的场景中尤为常见。

《夸克》非常好用的免费AI浏览器

下载APP查看