C++ 算法 upper_bound() 函数

C++ algorithm 库

定义和用法

upper_bound() 函数是一种高效算法，用于在已排序的数据范围内查找第一个大于指定上界的值。

注意：数据范围必须已经是有序的。如果数据未排序，函数可能返回错误结果。可使用 sort() 函数对数据范围进行排序。

数据范围通过迭代器指定。

实例

在已排序的 vector 中查找第一个大于 7 的值：

vector<int> numbers = {1, 7, 3, 5, 9, 2};
sort(numbers.begin(), numbers.end());  // 排序后：1,2,3,5,7,9
auto it = upper_bound(numbers.begin(), numbers.end(), 7);
if(it != numbers.end()) {
    cout << *it << " 是第一个大于 7  的值";  // 输出：9 是第一个大 于 7的值
} else {
    cout << "未找到大于上界值的元素";
}

亲自试一试

语法

upper_bound(iterator start, iterator end, <type> bound);

其中 <type> 表示数据范围包含的数据类型。

参数

参数 描述
start 必需。指向数据范围起始位置的迭代器。
end

必需。指向数据范围结束位置的迭代器。

将搜索到该位置之前的元素。
bound 必需。指定的上界值。

技术细节

返回：

指向第一个大于上界值的元素的迭代器。

若未找到满足条件的元素，则返回 end 迭代器。

说明：

  • 采用二分查找算法，时间复杂度为 O(log n)
  • 要求数据范围必须是有序的
  • 常用于有序容器的范围查询和插入位置确定

与 lower_bound() 的区别：

upper_bound() 返回第一个"大于"的值，而 lower_bound() 返回第一个"大于或等于"的值。

相关页面

教程：C++ 数据结构

教程：C++ 迭代器

教程：C++ 算法

C++ algorithm 库