c++ lower_bound 和 upper_bound区别

### C++ 中 `lower_bound` 和 `upper_bound` 的区别 #### 定义与功能 `lower_bound` 是用于查找第一个 **不小于目标值 (`target`) 的位置**，返回的是指向该元素的迭代器[^2]。 而 `upper_bound` 则是用于查找第一个 **大于目标值 (`target`) 的位置**，同样返回指向该元素的迭代器。 两者都基于二分查找实现，因此要求输入序列必须有序（通常是升序排列）。 --- #### 参数说明 两个函数具有相同的参数结构： ```cpp template<class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value); ``` - `first`: 起始地址或迭代器。 - `last`: 结束地址或迭代器（注意：此位置本身不会被访问）。 - `value`: 需要比较的目标值。 对于自定义排序规则的情况，还可以提供第四个参数——一个比较函数对象。 --- #### 使用场景对比 | 功能 | `lower_bound` | `upper_bound` | |-------------------------|-----------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------------| | 查找条件 | 找到第一个 **不小于** 给定值的位置 | 找到第一个 **严格大于** 给定值的位置 | | 应用场景 | 常见于需要找到某个范围起点的任务 | 常见于需要找到某个范围终点的任务 | | 返回结果特性 | 如果找不到符合条件的值，则返回最后一个可能的位置 (即 `end()` 或者超出当前容器的部分) | 同上 | --- #### 示例代码 以下是具体的使用示例： ```cpp #include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 2, 4, 6, 7, 9}; int target = 5; auto lb = std::lower_bound(vec.begin(), vec.end(), target); // 寻找 >=5 的第一个数 if (lb != vec.end()) { std::cout << "Lower bound of " << target << " is at index: " << std::distance(vec.begin(), lb) << ", Value: " << *lb << "\n"; } else { std::cout << "No element found that satisfies the condition.\n"; } auto ub = std::upper_bound(vec.begin(), vec.end(), target); // 寻找 >5 的第一个数 if (ub != vec.end()) { std::cout << "Upper bound of " << target << " is at index: " << std::distance(vec.begin(), ub) << ", Value: " << *ub << "\n"; } else { std::cout << "No element found that satisfies the condition.\n"; } return 0; } ``` 运行上述程序会得到如下输出： ``` Lower bound of 5 is at index: 3, Value: 6 Upper bound of 5 is at index: 3, Value: 6 ``` 这表明当目标值不存在时，两者的返回值可能是相同的。 --- #### 自定义排序规则扩展 如果希望按照降序或其他特定顺序来执行操作，可以传递额外的比较函数作为第四参数。例如： ```cpp std::vector<int> vec_desc = {9, 7, 6, 4, 2, 1}; auto custom_lb = std::lower_bound(vec_desc.begin(), vec_desc.end(), 5, [](const int &a, const int &b){return a > b;}); if (custom_lb != vec_desc.end()) { std::cout << "Custom Lower Bound Index: " << std::distance(vec_desc.begin(), custom_lb) << ", Value: " << *custom_lb << "\n"; } ``` 这里通过 lambda 表达式重新定义了比较逻辑以适应降序数组的需求。 ---