c++ upper_bound 和lower_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 表达式重新定义了比较逻辑以适应降序数组的需求。 ---

upper_bound和lower_bound是C++标准库中的两个函数，用于在有序的容器（例如数组或vector）中查找指定的元素。 upper_bound函数返回的是容器中第一个大于指定元素的位置，而lower_bound函数返回的是容器中第一个大于等于指定元素的位置。 这两个函数接收三个迭代器参数，分别是容器的起始位置、结束位置和要查找的元素。它们都使用了二分查找算法来实现，因此在有序容器中的查找速度非常快。 下面是它们的用法示例： int arr[] = {1, 2, 2, 3, 4, 4, 5}; vector<int> vec(arr, arr + 7); sort(vec.begin(), vec.end()); auto it1 = upper_bound(vec.begin(), vec.end(), 3); // 返回指向元素4的迭代器 auto it2 = lower_bound(vec.begin(), vec.end(), 4); // 返回指向元素4的迭代器 cout << "upper_bound: " << *it1 << endl; cout << "lower_bound: " << *it2 << endl; 输出结果为: upper_bound: 4 lower_bound: 4