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]。