企业官网建设流程全解析

廊坊网站推广排名,网络营销策划书的任务书,wordpress一键发布,怎么制作软件app教程前言 在算法竞赛和日常编程中#xff0c;二分查找是解决搜索问题的利器。C STL 中的 lower_bound 函数将二分查找封装得既优雅又高效。今天我们就来深入剖析这个强大的工具。 什么是 lower_bound#xff1f; lower_bound 是 C algorithm 头文件中的一个函数#…前言在算法竞赛和日常编程中二分查找是解决搜索问题的利器。C STL 中的lower_bound函数将二分查找封装得既优雅又高效。今天我们就来深入剖析这个强大的工具。什么是 lower_boundlower_bound是 Calgorithm头文件中的一个函数用于在有序序列中查找第一个大于等于目标值的元素位置。基本语法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() { vectorint 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第一个≥targettarget3第一个3的位置upper_bound第一个targettarget35的位置binary_search是否存在targettarget3true布尔值equal_range返回[lower, upper)target3[第一个3, 5)可视化演示数组[1, 3, 3, 5, 7, 9]情况1查找 target 3lower_bound 返回 ↑指向第一个3数组[1, 3, 3, 5, 7, 9]↑情况2查找 target 4lower_bound 返回 ↑指向5数组[1, 3, 3, 5, 7, 9]↑情况3查找 target 10lower_bound 返回 end()数组[1, 3, 3, 5, 7, 9] end()↑实战应用1.统计元素出现次数vectorint 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.在有序数组中插入元素vectorint 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(vectorint 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.数组必须有序// 错误示范 vectorint 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.获取索引的正确方式vectorint 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.处理找不到的情况vectorint 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(vectorint 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(vectorint 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(vectorint nums, int target) { return lower_bound(nums.begin(), nums.end(), target) - nums.begin(); }3.区间合并// 将新区间插入到有序区间列表中 vectorvectorint insertInterval(vectorvectorint intervals, vectorint newInterval) { // 找到插入位置 auto it lower_bound(intervals.begin(), intervals.end(), newInterval, [](const vectorint a, const vectorint b) { return a[0] b[0]; }); intervals.insert(it, newInterval); // ... 后续合并重叠区间 return intervals; }进阶技巧1.自定义比较函数struct Person { string name; int age; }; vectorPerson 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.在降序数组中使用vectorint nums {9, 7, 5, 3, 1}; // 在降序数组中查找需要自定义比较 auto it lower_bound(nums.begin(), nums.end(), 4, greaterint()); // 返回指向3的迭代器第一个≤4的元素实际上需要重新定义性能对比测试#include iostream #include vector #include algorithm #include chrono using namespace std; using namespace chrono; int main() { // 准备100万个数据 vectorint 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_castmicroseconds(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题