别再死记硬背二分法了！用C++ STL的lower_bound/upper_bound实战刷题（附LeetCode例题）-编程阁

二分查找进阶：用C++ STL工具提升算法实战效率

在算法面试和编程竞赛中，二分查找是最基础也最常考的算法之一。许多开发者习惯手写二分查找代码，却忽略了C++标准库中已经提供的强大工具——lower_bound和upper_bound。这些STL算法不仅能够减少代码量，还能避免常见的边界错误，让我们的解题过程更加高效可靠。

1. 为什么选择STL二分查找工具？

手写二分查找看似简单，实则暗藏许多陷阱。最常见的错误包括：

循环条件写成while(left < right)还是while(left <= right)？
更新边界时用right = mid还是right = mid - 1？
如何处理重复元素的情况？

这些问题在面试紧张的氛围下特别容易出错。而STL中的二分查找算法已经完美解决了这些边界条件问题，经过数十年的实践检验，其可靠性和效率都有保证。

lower_bound和upper_bound的核心优势在于：

统一接口：无论查找什么类型的数据，调用方式都保持一致
边界安全：自动处理所有可能的边界情况
泛型支持：适用于各种容器（vector、array、deque等）
性能保证：时间复杂度严格为O(log n)

2. lower_bound与upper_bound详解

2.1 lower_bound：查找第一个不小于目标值的位置

lower_bound返回第一个不小于目标值的元素位置。如果在vector v中查找值x：

auto it = std::lower_bound(v.begin(), v.end(), x);

如果x存在于v中，lower_bound返回第一个x的位置；如果x不存在，返回第一个大于x的位置；如果所有元素都小于x，返回v.end()。

2.2 upper_bound：查找第一个大于目标值的位置

upper_bound返回第一个大于目标值的元素位置：

auto it = std::upper_bound(v.begin(), v.end(), x);

对于存在的x，upper_bound返回最后一个x之后的位置；如果x不存在，行为与lower_bound相同。

2.3 两者配合使用

这两个函数经常一起使用来处理重复元素的情况。例如，要统计某个值x在有序数组中出现的次数：

int count = std::upper_bound(v.begin(), v.end(), x) - std::lower_bound(v.begin(), v.end(), x);

3. LeetCode实战应用

3.1 例题1：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

这是二分查找的经典题目，要求找出目标值的起始和结束位置。使用STL可以轻松解决：

vector<int> searchRange(vector<int>& nums, int target) { auto left = lower_bound(nums.begin(), nums.end(), target); if (left == nums.end() || *left != target) { return {-1, -1}; } auto right = upper_bound(nums.begin(), nums.end(), target); return {static_cast<int>(left - nums.begin()), static_cast<int>(right - nums.begin() - 1)}; }

对比手写二分查找的实现，STL版本更加简洁明了，且不容易出错。

3.2 例题2：寻找峰值（LeetCode 162）

虽然这不是典型的二分查找问题，但我们可以用lower_bound的变种来解决：

int findPeakElement(vector<int>& nums) { auto it = lower_bound(nums.begin(), nums.end(), INT_MAX, [](int a, int b) { return a > b; }); return it - nums.begin(); }

这里我们自定义了比较函数，使得查找方向反转。

4. 高级技巧与性能优化

4.1 自定义比较函数

STL二分查找算法允许传入自定义比较函数，这大大扩展了它们的应用场景。例如，查找第一个不小于x的偶数：

auto it = lower_bound(v.begin(), v.end(), x, [](int a, int b) { return (a % 2 == 0 ? a : a+1) < b; });

4.2 与其它STL算法配合

二分查找常与其它STL算法组合使用。例如，先排序再查找：

vector<int> v = {5, 3, 1, 4, 2}; sort(v.begin(), v.end()); // 先排序 bool found = binary_search(v.begin(), v.end(), 3); // 再查找

4.3 性能对比

下表对比了手写二分查找和STL实现的性能差异：

实现方式	代码行数	边界处理	可读性	执行效率
手写实现	15-20行	容易出错	一般	高
STL实现	1-2行	自动处理	优秀	极高

从实际测试来看，STL版本的执行效率通常比手写版本更高，因为STL经过了深度优化。

5. 常见问题与解决方案

5.1 如何处理未找到的情况？

当lower_bound或upper_bound没有找到目标值时，它们会返回容器的end()迭代器。在使用前应该先检查：

auto it = lower_bound(v.begin(), v.end(), x); if (it != v.end() && *it == x) { // 找到目标值 } else { // 未找到 }

5.2 如何查找最后一个小于x的元素？

这可以通过lower_bound来实现：

auto it = lower_bound(v.begin(), v.end(), x); if (it != v.begin()) { --it; // 这就是最后一个小于x的元素 }

5.3 在自定义结构体上使用二分查找

需要为结构体定义比较运算符或传入自定义比较函数：

struct Point { int x, y; bool operator<(const Point& p) const { return x < p.x || (x == p.x && y < p.y); } }; vector<Point> points; // ...填充数据... auto it = lower_bound(points.begin(), points.end(), Point{3, 4});