C++ 中 lower_bound 与 upper_bound 函数详解_lowerbound和upperbound

C++ 中 lower_bound 与 upper_bound 函数详解

文章目录

• • • C++ 中 `lower_bound` 与 `upper_bound` 函数详解
    • • **一、核心定义与区别**
      • **二、使用条件与时间复杂度**
      • **三、实际应用场景**
      • **四、注意事项与常见误区**
      • **五、代码示例**
      • **六、总结**

一、核心定义与区别

1. 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的索引位置

2. 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的位置

3. 关键区别

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

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

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

三、实际应用场景

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

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

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

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

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

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

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

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

四、注意事项与常见误区

1. 必须保证序列有序

   • 未排序时调用会导致未定义行为。例如，对乱序数组调用可能返回错误位置

2. 迭代器越界检查

   • 需验证返回值是否为end()，避免解引用无效迭代器

3. 自定义比较函数的一致性

   • 比较函数必须与序列排序规则一致。例如，降序序列需使用greater而非默认的 less

4. 等价元素的处理差异

   • 若需获取所有等价元素的范围，建议使用equal_range（返回lower_bound和upper_bound

     的 pair 结果）

五、代码示例

#include #include #include 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;}

六、总结

lower_bound 和 upper_bound 是处理有序序列的核心工具，适用于高效查找、统计和插入操作。使用时需严格保证序列的有序性，并根据场景选择是否需要自定义比较规则。通过灵活组合这两个函数，可以解决大多数与有序数据相关的算法问题。