C++ lower_bound与upper_bound用法_C++有序序列的二分查找利器

lower_bound返回首个不小于目标值的迭代器，upper_bound返回首个大于目标值的迭代器，二者结合可确定元素出现区间。例如在升序数组{1,2,4,4,5,7}中查找4，lower_bound指向索引2，upper_bound指向索引4，差值为出现次数2。降序排列时需传入greater<int>()等自定义比较函数，确保与排序规则一致。使用前必须保证序列有序，可高效实现查找、去重、插入等操作。

在C++中，lower_bound 和 upper_bound 是处理有序序列时非常高效的二分查找工具，定义于 <algorithm> 头文件中。它们能快速定位目标值的位置，常用于去重、插入排序、区间统计等场景。

lower_bound：查找第一个不小于目标值的位置

函数作用：在有序区间 [first, last) 中，返回指向第一个元素位置，其值大于等于给定值 val 的迭代器。

使用前提：序列必须按升序排列（或按自定义比较规则有序）。

vector<int> nums = {1, 2, 4, 4, 5, 7};
auto it = lower_bound(nums.begin(), nums.end(), 4);
cout << "下界索引: " << (it - nums.begin()); // 输出 2

若查找值为 3，则返回指向 4（索引2）的迭代器，因为它是第一个 ≥3 的元素。

立即学习“C++免费学习笔记（深入）”；

upper_bound：查找第一个大于目标值的位置

函数作用：返回指向第一个元素位置，其值严格大于给定值 val 的迭代器。

vector<int> nums = {1, 2, 4, 4, 5, 7};
auto it = upper_bound(nums.begin(), nums.end(), 4);
cout << "上界索引: " << (it - nums.begin()); // 输出 4

结果指向值为5的元素，即第一个 >4 的位置。

配合使用：确定值的完整出现区间

当需要找出某个值在有序序列中的所有出现范围时，可结合两者：

int val = 4;
auto left = lower_bound(nums.begin(), nums.end(), val);
auto right = upper_bound(nums.begin(), nums.end(), val);
cout << "值 " << val << " 出现次数: " << (right - left);

这段代码输出 2，表示4出现了两次。

支持自定义比较函数

如果容器按降序排列，需传入比较函数，例如 greater<int>()：

vector<int> desc = {7, 5, 4, 4, 2, 1};
auto it = lower_bound(desc.begin(), desc.end(), 4, greater<int>());
// 找到第一个 ≤4 的位置（降序中“不小于”含义改变）

此时逻辑基于自定义顺序，确保比较规则与排序一致。

基本上就这些。熟练使用 lower_bound 和 upper_bound，能避免手写二分错误，提升编码效率和准确性。注意使用前务必保证序列有序。

以上就是C++ lower_bound与upper_bound用法_C++有序序列的二分查找利器的详细内容，更多请关注php中文网其它相关文章！