C++ 中 lower_bound 与 upper_bound 函数详解

C++ 中 `lower_bound` 与 `upper_bound` 函数详解

一、核心定义与区别

lower_bound
- 作用：在有序序列中查找第一个不小于目标值的元素位置
- 返回值：若目标值存在，返回第一个匹配元素的迭代器；若不存在，返回首个大于目标值的元素的迭代器
- 示例：在序列{1,2,4,4,5} 中查找 4，返回第一个4 的位置（索引 2）
- 用lower_bound在{12,15,17,19,20,22,23,26,29,35,40,51}，查找21时返回22的索引位置
upper_bound
- 作用：在有序序列中查找第一个大于目标值的元素位置
- 返回值：若目标值存在，返回最后一个匹配元素的下一个位置；若不存在，行为与lower_bound一致
- 示例：在相同序列{1,2,4,4,5}中查找4，返回第一个 5的位置（索引 4）
- 用up_bound在{12,15,17,19,20,22,23,26,29,35,40,51}，查找21时返回22的位置

关键区别

特性	`lower_bound`	`upper_bound`
等价元素处理	指向第一个等价元素	指向最后一个等价元素的下一个位置
插入位置	插入后位于相同元素之前	插入后位于相同元素之后
目标值不存在时返回值	第一个大于目标值的元素位置	同上

二、使用条件与时间复杂度

前提条件
- 序列必须已按升序排列（或按自定义比较规则有序）。若未排序，结果未定义。
时间复杂度
- 均为 O(log n)，基于二分查找实现

三、实际应用场景

检查元素是否存在
结合 lower_bound 的返回值与目标值比较：

1	bool exists = (lower_bound(v.begin(), v.end(), target) != v.end()) && (*it == target);

统计元素出现次数
使用 upper_bound - lower_bound 计算区间跨度：

1	int count = upper_bound(v.begin(), v.end(), target) - lower_bound(v.begin(), v.end(), target);

自定义排序规则
支持传入比较函数，处理复杂数据结构或非默认排序：

1
2
3

// 按个位数排序的数组
bool cmp(int a, int b) { return a % 10 < b % 10; }
auto it = lower_bound(arr, arr + n, 36, cmp); // 查找个位数 >=6 的第一个元素

插入元素保持有序性
在有序容器中插入新元素时，确定插入位置

1 2	auto pos = upper_bound(v.begin(), v.end(), new_value); v.insert(pos, new_value); // 插入后序列仍有序

四、注意事项与常见误区

必须保证序列有序
- 未排序时调用会导致未定义行为。例如，对乱序数组调用可能返回错误位置
迭代器越界检查
- 需验证返回值是否为end()，避免解引用无效迭代器
自定义比较函数的一致性
- 比较函数必须与序列排序规则一致。例如，降序序列需使用greater而非默认的 less
等价元素的处理差异
- 若需获取所有等价元素的范围，建议使用equal_range（返回lower_bound和upper_bound
  
  的 pair 结果）

五、代码示例

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {1, 2, 4, 4, 5, 7, 8};
    int target = 4;

    // lower_bound 示例
    auto low = lower_bound(v.begin(), v.end(), target);
    cout << "lower_bound 位置: " << (low - v.begin()) << "，值: " << *low << endl; // 输出 2, 4

    // upper_bound 示例
    auto up = upper_bound(v.begin(), v.end(), target);
    cout << "upper_bound 位置: " << (up - v.begin()) << "，值: " << *up << endl; // 输出 4, 5

    return 0;
}