南京市网站建设_网站建设公司_后端开发_seo优化

前言

在算法竞赛和日常编程中，二分查找是解决搜索问题的利器。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, 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; }

最佳实践建议

1. 总是先排序：使用前确保序列有序

2. 检查返回值：总是验证返回的迭代器是否有效

3. 优先使用STL：比手写二分查找更可靠

4. 注意边界：理解[first, last)的半开半闭区间

5. 利用类型推导：使用auto简化代码

总结

lower_bound是 C++ 程序员工具箱中的瑞士军刀：

• 高效：O(log n) 时间复杂度

• 通用：适用于任何有序序列

• 安全：STL 实现经过充分测试

• 灵活：支持自定义比较函数

掌握lower_bound不仅能提高编码效率，更能帮助你深入理解二分查找思想。下次遇到有序数组的查找问题，不妨先想想：能不能用lower_bound解决？

学习资源推荐：

• C++ Reference: lower_bound

• 《C++ Primer》第10章：泛型算法

• LeetCode 练习：35、34、704、278题