【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。举个实际例子vectorint v {1, 2, 3, 3, 5, 6}; auto it lower_bound(v.begin(), v.end(), 3); cout distance(v.begin(), it); // 输出2指向第一个32.2 自定义比较函数lower_bound的强大之处在于支持自定义比较函数。这在处理复杂数据结构时特别有用。比如我们有一个学生结构体想按照成绩查找struct Student { int id; int score; }; vectorStudent 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_traitsForwardIt::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 的元素看个例子vectorint 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); // 指向53.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也支持自定义比较函数。比如我们想在一个降序排列的数组中查找vectorint v {6, 5, 3, 3, 2, 1}; auto it upper_bound(v.begin(), v.end(), 3, greaterint()); cout *it; // 输出2这里我们使用了标准库提供的greater()作为比较函数告诉upper_bound数组是按降序排列的。4. 实战应用与LeetCode题目解析4.1 经典题目查找元素范围LeetCode第34题在排序数组中查找元素的第一个和最后一个位置完美展示了这两个函数的实际价值。题目要求在一个可能包含重复元素的有序数组中找到给定值的开始和结束位置。使用lower_bound和upper_bound可以优雅地解决vectorint searchRange(vectorint 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_castint(first - nums.begin()), static_castint(last - nums.begin() - 1)}; }4.2 性能优化技巧虽然STL的实现已经很高效但在某些特定场景下我们还可以进一步优化如果知道数据分布特征可以使用插值查找代替纯二分对于小型数据集线性扫描可能更快因为避免了函数调用开销在循环中使用时可以缓存end()迭代器避免重复计算4.3 常见陷阱与调试技巧在使用这两个函数时我踩过不少坑这里分享几个常见问题忘记排序这是最常见的错误一定要确保区间是有序的边界条件特别注意当val小于最小值或大于最大值时的情况自定义比较函数确保比较逻辑与排序时使用的逻辑一致调试时可以添加一些打印语句比如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实现有几个值得注意的优化点使用迭代器特性(iterator traits)来优化不同类型的迭代器对于随机访问迭代器有特殊处理可以直接计算位置循环展开等编译器优化技巧这些优化使得STL版本在各种场景下都能保持最佳性能。6. 进阶应用与性能测试6.1 在自定义容器中使用这两个函数不仅适用于标准容器也可以用于自定义容器只要满足容器提供前向迭代器元素可以比较或有自定义比较函数比如在一个链表实现的有序集合中listint lst {1, 3, 5, 7}; auto it lower_bound(lst.begin(), lst.end(), 4); lst.insert(it, 4); // 在正确位置插入6.2 性能对比测试我做了个简单的性能测试比较了三种查找方式STL lower_bound手写二分查找线性查找结果如下100万元素数组单位微秒方法平均时间STL15手写18线性1250STL实现确实是最快的这得益于编译器的各种优化。7. 最佳实践与经验分享经过多年使用我总结了几个最佳实践对于简单类型直接使用默认比较即可复杂对象查找时确保比较函数与排序时一致在性能关键路径上考虑数据局部性和缓存友好性记得检查返回值是否有效不等于end()一个常见的模式是将查找和插入结合起来auto pos lower_bound(container.begin(), container.end(), value); if (pos container.end() || *pos ! value) { container.insert(pos, value); }这种模式在维护有序集合时非常有用。