【C++】 深入剖析 lower_bound 和 upper_bound 的二分查找奥秘（附实战代码）

1. 二分查找的前世今生

我第一次接触二分查找是在大学的数据结构课上，当时觉得这个算法简直太神奇了——只需要O(log n)的时间复杂度就能在有序数组中快速定位元素。后来在LeetCode刷题时，发现很多题目都需要用到它的变种，特别是STL中的lower_bound和upper_bound函数。

二分查找的核心思想很简单：每次都将搜索范围缩小一半。想象一下你在玩猜数字游戏，对方心里想了一个1-100的数字，你每次猜中间值，对方告诉你大了还是小了，这样最多7次就能猜中。这就是二分查找的精髓。

在C++中，标准库已经为我们封装好了高效的二分查找实现，其中lower_bound和upper_bound是最常用的两个函数。它们都定义在头文件中，底层实现都是基于二分查找，但在具体行为上有些微妙的区别。

2. lower_bound函数深度解析

2.1 基本用法与原理

lower_bound的函数原型有两种形式：

template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val); template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

这个函数的作用是在有序区间[first, last)中查找第一个不小于val的元素位置。如果所有元素都小于val，则返回last。

举个实际例子：

vector<int> v = {1, 2, 3, 3, 5, 6}; auto it = lower_bound(v.begin(), v.end(), 3); cout << distance(v.begin(), it); // 输出2，指向第一个3

2.2 自定义比较函数

lower_bound的强大之处在于支持自定义比较函数。这在处理复杂数据结构时特别有用。比如我们有一个学生结构体，想按照成绩查找：

struct Student { int id; int score; }; vector<Student> students = {{1, 80}, {2, 85}, {3, 90}}; auto comp = [](const Student& s, int val) { return s.score < val; }; auto it = lower_bound(students.begin(), students.end(), 85, comp);

这里我们定义了一个lambda表达式作为比较函数，告诉lower_bound如何比较Student对象和查找值。

2.3 底层实现剖析

理解lower_bound的底层实现对我们正确使用它很有帮助。下面是一个简化版的实现：

template <class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& val) { ForwardIt it; typename std::iterator_traits<ForwardIt>::difference_type count, step; count = std::distance(first, last); while (count > 0) { it = first; step = count / 2; std::advance(it, step); if (*it < val) { first = ++it; count -= step + 1; } else { count = step; } } return first; }

这个实现展示了二分查找的精髓：通过不断缩小搜索范围来快速定位目标位置。

3. upper_bound函数全面掌握

3.1 与lower_bound的区别

upper_bound和lower_bound非常相似，但有一个关键区别：它返回的是第一个大于val的元素位置，而不是不小于。用数学符号表示就是：

• lower_bound: 第一个 ≥ val 的元素
• upper_bound: 第一个 > val 的元素

看个例子：

vector<int> v = {1, 2, 3, 3, 5, 6}; auto lb = lower_bound(v.begin(), v.end(), 3); // 指向第一个3 auto ub = upper_bound(v.begin(), v.end(), 3); // 指向5

3.2 实际应用场景

upper_bound特别适合处理存在重复元素的情况。比如统计某个值在有序数组中出现的次数：

int count = upper_bound(v.begin(), v.end(), val) - lower_bound(v.begin(), v.end(), val);

这个方法比线性扫描高效得多，特别是当数组很大时。

3.3 自定义比较示例

和lower_bound一样，upper_bound也支持自定义比较函数。比如我们想在一个降序排列的数组中查找：

vector<int> v = {6, 5, 3, 3, 2, 1}; auto it = upper_bound(v.begin(), v.end(), 3, greater<int>()); cout << *it; // 输出2

这里我们使用了标准库提供的greater()作为比较函数，告诉upper_bound数组是按降序排列的。

4. 实战应用与LeetCode题目解析

4.1 经典题目：查找元素范围

LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"完美展示了这两个函数的实际价值。题目要求在一个可能包含重复元素的有序数组中，找到给定值的开始和结束位置。

使用lower_bound和upper_bound可以优雅地解决：

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

4.2 性能优化技巧

虽然STL的实现已经很高效，但在某些特定场景下我们还可以进一步优化：

1. 如果知道数据分布特征，可以使用插值查找代替纯二分
2. 对于小型数据集，线性扫描可能更快（因为避免了函数调用开销）
3. 在循环中使用时，可以缓存end()迭代器避免重复计算

4.3 常见陷阱与调试技巧

在使用这两个函数时，我踩过不少坑，这里分享几个常见问题：

1. 忘记排序：这是最常见的错误，一定要确保区间是有序的
2. 边界条件：特别注意当val小于最小值或大于最大值时的情况
3. 自定义比较函数：确保比较逻辑与排序时使用的逻辑一致

调试时可以添加一些打印语句，比如：

cout << "Searching for " << val << " in range [" << *first << ", " << *(last-1) << "]\n";

5. 手写实现与STL源码对比

5.1 手写lower_bound

理解STL实现的最好方式就是自己实现一个简化版。下面是我的实现：

template <typename It, typename T> It my_lower_bound(It first, It last, const T& val) { It it; size_t count = distance(first, last); size_t step; while (count > 0) { it = first; step = count / 2; advance(it, step); if (*it < val) { first = ++it; count -= step + 1; } else { count = step; } } return first; }

这个实现和STL的思路基本一致，但省略了一些优化和泛型处理。

5.2 STL源码亮点分析

查看GCC的STL实现，有几个值得注意的优化点：

1. 使用迭代器特性(iterator traits)来优化不同类型的迭代器
2. 对于随机访问迭代器有特殊处理，可以直接计算位置
3. 循环展开等编译器优化技巧

这些优化使得STL版本在各种场景下都能保持最佳性能。

6. 进阶应用与性能测试

6.1 在自定义容器中使用

这两个函数不仅适用于标准容器，也可以用于自定义容器，只要满足：

1. 容器提供前向迭代器
2. 元素可以比较（或有自定义比较函数）

比如在一个链表实现的有序集合中：

list<int> lst = {1, 3, 5, 7}; auto it = lower_bound(lst.begin(), lst.end(), 4); lst.insert(it, 4); // 在正确位置插入

6.2 性能对比测试

我做了个简单的性能测试，比较了三种查找方式：

1. STL lower_bound
2. 手写二分查找
3. 线性查找

结果如下（100万元素数组，单位：微秒）：

STL实现确实是最快的，这得益于编译器的各种优化。

7. 最佳实践与经验分享

经过多年使用，我总结了几个最佳实践：

1. 对于简单类型，直接使用默认比较即可
2. 复杂对象查找时，确保比较函数与排序时一致
3. 在性能关键路径上，考虑数据局部性和缓存友好性
4. 记得检查返回值是否有效（不等于end()）

一个常见的模式是将查找和插入结合起来：

auto pos = lower_bound(container.begin(), container.end(), value); if (pos == container.end() || *pos != value) { container.insert(pos, value); }

这种模式在维护有序集合时非常有用。