前言
在算法竞赛和日常编程中，二分查找是解决搜索问题的利器。C++ STL 中的lower_bound函数将二分查找封装得既优雅又高效。今天我们就来深入剖析这个强大的工具。
什么是 lower_bound？
lower_bound是 C++<algorithm>头文件中的一个函数，用于在有序序列中查找第一个大于等于目标值的元素位置。
基本语法
template< class ForwardIt, class T > ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );参数：
first,last：定义搜索范围的迭代器value：要查找的目标值
返回值：
指向第一个≥ value元素的迭代器
如果所有元素都 < value，返回
last
直观理解
想象一下，你有一排按身高排序的学生：
[150cm, 155cm, 160cm, 160cm, 165cm, 170cm]
当我们要找第一个≥ 160cm的学生时：
lower_bound会指向第一个 160cm 的学生（索引2）即使后面还有更多 160cm 的学生，它只返回第一个
基本用法示例
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> nums = {1, 2, 4, 4, 5, 6, 7}; // 查找第一个 >= 4 的元素 auto it = lower_bound(nums.begin(), nums.end(), 4); if (it != nums.end()) { cout << "找到位置: " << (it - nums.begin()) << endl; // 输出: 2 cout << "对应值: " << *it << endl; // 输出: 4 } return 0; }lower_bound 家族对比
| 函数 | 功能描述 | 示例（数组[1,3,3,5]） | 返回值 |
|---|---|---|---|
lower_bound | 第一个≥target | target=3 | 第一个3的位置 |
upper_bound | 第一个>target | target=3 | 5的位置 |
binary_search | 是否存在target | target=3 | true（布尔值） |
equal_range | 返回[lower, upper) | target=3 | [第一个3, 5) |
可视化演示
数组：[1, 3, 3, 5, 7, 9]
情况1：查找 target = 3
lower_bound 返回 ↑（指向第一个3）
数组：[1, 3, 3, 5, 7, 9]
↑
情况2：查找 target = 4
lower_bound 返回 ↑（指向5）
数组：[1, 3, 3, 5, 7, 9]
↑
情况3：查找 target = 10
lower_bound 返回 end()
数组：[1, 3, 3, 5, 7, 9] end()
↑
实战应用
1.统计元素出现次数
vector<int> nums = {1, 2, 2, 2, 3, 4}; int target = 2; auto left = lower_bound(nums.begin(), nums.end(), target); auto right = upper_bound(nums.begin(), nums.end(), target); int count = right - left; // 3（有3个2） cout << target << "出现了" << count << "次" << endl;2.在有序数组中插入元素
vector<int> nums = {1, 3, 5, 7}; int new_num = 4; // 找到插入位置（保持有序） auto pos = lower_bound(nums.begin(), nums.end(), new_num); nums.insert(pos, new_num); // 插入到合适位置 // 结果：[1, 3, 4, 5, 7]3.解决"差值配对"问题
// 问题：统计有多少对数的差等于c int countPairs(vector<int>& nums, int c) { sort(nums.begin(), nums.end()); int ans = 0; for(int i = 0; i < nums.size(); i++) { int target = nums[i] + c; ans += upper_bound(nums.begin(), nums.end(), target) - lower_bound(nums.begin(), nums.end(), target); } return ans; }注意事项
1.数组必须有序
// 错误示范 vector<int> nums = {5, 1, 3, 2}; auto it = lower_bound(nums.begin(), nums.end(), 3); // 未定义行为！ // 正确做法 sort(nums.begin(), nums.end()); // 先排序 auto it = lower_bound(nums.begin(), nums.end(), 3); // 正确2.获取索引的正确方式
vector<int> nums = {10, 20, 30, 40}; auto it = lower_bound(nums.begin(), nums.end(), 25); if (it != nums.end()) { int index = it - nums.begin(); // 获取索引 // 不要用 distance()，效率较低 }3.处理找不到的情况
vector<int> nums = {1, 2, 3}; auto it = lower_bound(nums.begin(), nums.end(), 5); if (it == nums.end()) { cout << "所有元素都小于5" << endl; } else { cout << "找到元素：" << *it << endl; }性能分析
时间复杂度：O(log n)
每次将搜索范围减半
即使处理百万级数据也只需约20次比较
空间复杂度：O(1)
只使用常数额外空间
手动实现 lower_bound
理解原理有助于更好使用：
// 手写 lower_bound 实现 int my_lower_bound(vector<int>& nums, int target) { int left = 0; int right = nums.size(); // 注意：不是 size()-1 while (left < right) { int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] < target) { left = mid + 1; // 目标在右侧 } else { right = mid; // 目标在左侧或当前位置 } } return left; // 第一个≥target的位置 }常见面试题应用
1.寻找第一个出现的位置
// 在有序有重复数组中找元素的第一个位置 int firstPosition(vector<int>& nums, int target) { auto it = lower_bound(nums.begin(), nums.end(), target); if (it != nums.end() && *it == target) { return it - nums.begin(); } return -1; }2.查找插入位置
// LeetCode 35. 搜索插入位置 int searchInsert(vector<int>& nums, int target) { return lower_bound(nums.begin(), nums.end(), target) - nums.begin(); }3.区间合并
// 将新区间插入到有序区间列表中 vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) { // 找到插入位置 auto it = lower_bound(intervals.begin(), intervals.end(), newInterval, [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }); intervals.insert(it, newInterval); // ... 后续合并重叠区间 return intervals; }进阶技巧
1.自定义比较函数
struct Person { string name; int age; }; vector<Person> people = {{"Alice", 20}, {"Bob", 25}, {"Charlie", 25}, {"David", 30}}; // 按年龄查找 auto it = lower_bound(people.begin(), people.end(), 25, [](const Person& p, int age) { return p.age < age; // 自定义比较 });2.在降序数组中使用
vector<int> nums = {9, 7, 5, 3, 1}; // 在降序数组中查找，需要自定义比较 auto it = lower_bound(nums.begin(), nums.end(), 4, greater<int>()); // 返回指向3的迭代器（第一个≤4的元素？实际上需要重新定义）性能对比测试
#include <iostream> #include <vector> #include <algorithm> #include <chrono> using namespace std; using namespace chrono; int main() { // 准备100万个数据 vector<int> nums(1000000); for(int i = 0; i < 1000000; i++) { nums[i] = i * 2; // 偶数序列 } // 测试 lower_bound auto start = high_resolution_clock::now(); for(int i = 0; i < 1000; i++) { auto it = lower_bound(nums.begin(), nums.end(), i * 100); } auto end = high_resolution_clock::now(); auto duration = duration_cast<microseconds>(end - start); cout << "1000次查找耗时: " << duration.count() << " 微秒" << endl; cout << "平均每次查找: " << duration.count() / 1000.0 << " 微秒" << endl; return 0; }最佳实践建议
总是先排序：使用前确保序列有序
检查返回值：总是验证返回的迭代器是否有效
优先使用STL：比手写二分查找更可靠
注意边界：理解
[first, last)的半开半闭区间利用类型推导：使用
auto简化代码
总结
lower_bound是 C++ 程序员工具箱中的瑞士军刀：
高效：O(log n) 时间复杂度
通用：适用于任何有序序列
安全：STL 实现经过充分测试
灵活：支持自定义比较函数
掌握lower_bound不仅能提高编码效率，更能帮助你深入理解二分查找思想。下次遇到有序数组的查找问题，不妨先想想：能不能用lower_bound解决？
学习资源推荐：
C++ Reference: lower_bound
《C++ Primer》第10章：泛型算法
LeetCode 练习：35、34、704、278题
