lower_bound 和 upper_bound

### C++ `lower_bound` 和 `upper_bound` 的用法与区别 #### 函数定义 在C++标准库中，`std::lower_bound` 和 `std::upper_bound` 是用于二分查找的算法函数。它们通常被用来在一个已排序的序列中找到特定值的第一个位置或者最后一个位置之后的位置。 - **`std::lower_bound`**: 返回指向第一个不小于目标值的元素的迭代器[^4]。 - **`std::upper_bound`**: 返回指向上一个大于目标值的元素的迭代器[^5]。 这两个函数都要求输入容器中的数据是有序的（通常是升序）。如果未按顺序排列，则结果不可预测。 #### 参数说明 两者均接受四个参数： 1. 起始迭代器 (`first`)：指定要搜索范围的起始地址。 2. 结束迭代器 (`last`)：指定要搜索范围结束后的下一个地址。 3. 查找的目标值 (`value`)：需要定位的具体数值。 4. 可选比较函数对象/谓词表达式（默认为 `<` 运算符）。 #### 使用示例 以下是两个函数的基本使用方法： ```cpp #include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 2, 4, 4, 5, 7}; int value_to_find = 4; auto lb_it = std::lower_bound(vec.begin(), vec.end(), value_to_find); if(lb_it != vec.end()) { std::cout << "Lower bound points to: " << *lb_it << '\n'; } else { std::cout << "Value not found\n"; } auto ub_it = std::upper_bound(vec.begin(), vec.end(), value_to_find); if(ub_it != vec.end()) { std::cout << "Upper bound points to: " << *ub_it << '\n'; } else { std::cout << "No element greater than the given value.\n"; } } ``` 在这个例子中，对于数组 `{1, 2, 4, 4, 5, 7}` 中寻找值 `4`， - `lower_bound` 将返回第一个等于或大于 `4` 的位置，即第二个 `4` 所处的位置； - `upper_bound` 则会跳过所有的 `4` 并停在紧随其后的更大数 `5` 上面[^6]。 #### 主要差异 | 特性 | `std::lower_bound` | `std::upper_bound` | |---------------------|---------------------------------------------|------------------------------------------| | 定义 | 第一个小于或等于给定值的位置 | 第一个严格大于给定值的位置 | | 时间复杂度 | O(log n) | O(log n) | 因此，在处理重复项时，`std::lower_bound` 经常用于获取某个键首次出现的地方；而 `std::upper_bound` 更适合确定该键最后一次出现之后的位置[^7]。

<think>好的，我现在需要帮助用户了解C++ STL中lower_bound和upper_bound的用法。用户可能已经接触过map和set这些容器，但不太清楚这两个函数的区别和应用场景。首先，我得回顾一下这两个函数的基本定义和用途。 根据用户提供的引用资料，特别是引用3和4，里面提到了upper_bound的用法示例，比如在set中使用upper_bound查找第一个大于key的元素。但用户现在想同时了解lower_bound和upper_bound，所以我需要详细解释两者的区别。 首先，lower_bound返回的是第一个大于或等于目标值的元素位置，而upper_bound返回的是第一个大于目标值的元素位置。这在有序容器中非常有用，比如在排序数组、vector、set或map中。这两个函数常用于确定插入位置或者查找元素范围。 接下来，我需要考虑用户可能的实际应用场景。比如在有序区间内插入元素时，可以用lower_bound找到合适的插入点；或者在处理范围查询时，比如统计某个区间内的元素数量，可以用这两个函数确定上下界。例如，用户可能想在一个已排序的vector中找到所有大于等于5且小于10的元素，这时候lower_bound(5)和upper_bound(10)就能确定这个区间。 然后，我需要检查用户提供的引用内容是否有相关例子或代码片段。引用3中提到了upper_bound的使用方法，引用4展示了erase和find的结合使用。虽然这些例子没有直接展示lower_bound，但可以结合这些例子来说明两者的区别。例如，在set中，使用lower_bound找到第一个不小于key的元素，而upper_bound则是第一个大于key的，这样在删除某个范围的元素时，可以配合使用这两个函数。 还需要注意这两个函数的时间复杂度，因为它们通常基于二分查找实现，时间复杂度为O(log n)，适用于有序容器。但如果是无序结构，比如unordered_map，这两个函数可能不可用，这时候用户可能需要先对容器进行排序，或者使用其他数据结构。 另外，用户可能在处理需要频繁查找和插入有序数据的场景中使用这些函数，比如维护一个实时更新的排行榜，或者处理时间序列数据。这时候正确使用lower_bound和upper_bound可以提高效率。 最后，我需要确保回答结构清晰，分点说明两者的定义、使用场景、代码示例以及注意事项。同时，根据用户要求生成相关问题，比如它们的区别、应用实例或底层实现原理。这样用户能够全面理解并应用到实际编程中。</think>### C++ STL中lower_bound与upper_bound用法解析 #### 一、基础定义与核心差异 1. **lower_bound** 在**有序区间**中返回第一个**大于或等于目标值**的元素迭代器 数学表达式：查找第一个满足$val \geq key$的元素位置 2. **upper_bound** 在**有序区间**中返回第一个**大于目标值**的元素迭代器 数学表达式：查找第一个满足$val > key$的元素位置 ```cpp // 示例：查找有序数组中的范围 vector<int> arr = {1,3,5,7,9}; auto lower = lower_bound(arr.begin(), arr.end(), 5); // 指向5 auto upper = upper_bound(arr.begin(), arr.end(), 5); // 指向7 ``` #### 二、典型应用场景 1. **范围查询** ```cpp // 统计[5,8)区间内的元素数量 set<int> s = {1,3,5,7,9}; auto start = s.lower_bound(5); // 包含5 auto end = s.upper_bound(8); // 不包含8 int count = distance(start, end); // 返回2（5,7） ``` 2. **插入位置确定** ```cpp // 在有序vector中插入元素保持有序性 vector<string> words = {"apple", "banana"}; auto pos = lower_bound(words.begin(), words.end(), "cherry"); words.insert(pos, "cherry"); // 插入到正确位置 ``` 3. **区间删除** ```cpp // 删除所有大于等于3且小于6的元素（引用4的扩展） set<int> myset = {1,2,3,4,5}; myset.erase(myset.lower_bound(3), myset.upper_bound(5)); // 剩余元素：{1,2} ``` #### 三、重要注意事项 1. **容器必须有序** 这两个函数基于二分查找实现，时间复杂度为$O(\log n)$，仅适用于有序容器如`set/map`或已排序的`vector`[^2] 2. **自定义比较函数** ```cpp // 自定义结构体排序规则 struct Person { int age; string name; }; vector<Person> people; // 按年龄升序排列后查找 auto it = lower_bound(people.begin(), people.end(), [](const Person& p, int age){ return p.age < age; }); ``` 3. **返回值验证** 需要检查返回迭代器是否有效，避免越界访问： ```cpp if(lower != container.end()) { // 安全操作 } ``` #### 四、关联容器特例 在`set/map`中可直接调用成员函数： ```cpp set<int> s = {1,3,5}; auto it = s.lower_bound(2); // 返回指向3的迭代器 map<string, int> m; m["apple"] = 5; auto mit = m.upper_bound("app"); // 查找第一个key大于"app"的条目 ```