C++ 算法 lower_bound() 函数

C++ algorithm 库

定义和用法

lower_bound() 函数是一种高效算法，用于在已排序的数据范围中查找首个不小于指定下界的元素。

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

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

实例

在 vector 中查找首个不小于 4 的元素：

vector<int> numbers = {1, 7, 3, 5, 9, 2};
sort(numbers.begin(), numbers.end());  // 先排序：1,2,3,5,7,9
auto it = lower_bound(numbers.begin(), numbers.end(), 4);
if (it != numbers.end()) {
    cout << *it << " 是首个不小于 4 的值";  // 输出：5 是首个不小于4的值
} else {
    cout << "未找到满足下界要求的元素";
}

亲自试一试

语法

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

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

参数

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

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

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

技术细节

返回：

指向首个不小于下界值的元素的迭代器。

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

说明：

该函数采用二分查找算法，时间复杂度为 O(log n)，要求数据范围必须是有序的。

相关页面

教程：C++ 数据结构

教程：C++ 迭代器

教程：C++ 算法

C++ algorithm 库