别再手动写二分查找了！用C++ STL的lower_bound和upper_bound函数5分钟搞定

别再手动写二分查找了用C STL的lower_bound和upper_bound函数5分钟搞定在算法竞赛和日常开发中二分查找是一种基础但极其重要的算法。很多开发者虽然理解其原理却仍然习惯手动编写循环来实现。这不仅效率低下还容易引入差一错误。本文将带你彻底转向更高效、更安全的STL二分查找方案。C标准模板库(STL)提供的lower_bound和upper_bound函数封装了经过严格优化的二分查找实现。它们不仅能处理简单查找任务还能优雅解决第一个大于等于、最后一个等于等复杂边界问题。掌握这两个函数你可以在LeetCode刷题、日志分析等场景中节省大量调试时间。1. 为什么应该放弃手写二分查找手动实现二分查找看似简单实则暗藏诸多陷阱。最常见的差一错误包括循环条件写成while(l r)还是while(l r)中间值计算使用(lr)/2可能导致的整数溢出更新边界时使用l mid还是l mid 1这些问题在压力环境下尤其容易暴露。相比之下STL函数具有三大优势零错误率由标准库维护者精心实现和测试高性能采用最优化的迭代器操作和分支预测表达清晰函数名直接体现查找语义考虑这个典型场景在有序数组[1,2,2,3,4,4,4,5]中查找数字4的所有出现位置。手动实现需要约15行代码而使用STL仅需auto first lower_bound(v.begin(), v.end(), 4); auto last upper_bound(v.begin(), v.end(), 4);2. lower_bound与upper_bound的核心区别这两个函数都作用于已排序的序列但返回位置有微妙差异函数查找条件返回值等效手写代码lower_bound第一个≥x的元素迭代器if(arr[mid] x) r mid;upper_bound第一个x的元素迭代器if(arr[mid] x) r mid;关键记忆点lower_bound的lower意味着包含等于的情况upper_bound的upper意味着严格大于实际应用时这两个函数经常配合使用查找等于x的范围[lower_bound, upper_bound)统计x的出现次数upper_bound - lower_bound3. 从迭代器到实际下标的转换技巧STL函数返回的是迭代器但实际开发中我们通常需要数组下标。转换方法有两种方法一减去容器起始迭代器vectorint v {1,2,3,4,5}; size_t index lower_bound(v.begin(), v.end(), 3) - v.begin();方法二使用C数组的指针算术int arr[] {1,2,3,4,5}; size_t index lower_bound(arr, arr5, 3) - arr;注意当查找失败时函数返回结束迭代器(等同于v.end()或arrsize)此时计算的下标等于容器大小使用前必须检查边界。4. 实战应用LeetCode经典问题解析4.1 数的范围查找元素首次和末次出现位置这是最直接的二分查找应用。给定升序数组和目标值找到该值的起始和结束位置。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 {first - nums.begin(), last - nums.begin() - 1}; }4.2 统计有序矩阵中小于某值的元素个数给定每行每列都升序排列的矩阵统计所有小于给定值的元素数量。int countLessThan(vectorvectorint matrix, int target) { int count 0; for(auto row : matrix) { count upper_bound(row.begin(), row.end(), target) - row.begin(); } return count; }4.3 寻找两个有序数组的中位数这是二分查找的高阶应用通过lower_bound可以优雅实现double findMedianSortedArrays(vectorint nums1, vectorint nums2) { if(nums1.size() nums2.size()) return findMedianSortedArrays(nums2, nums1); int m nums1.size(), n nums2.size(); int left 0, right m; while(left right) { int i (left right) / 2; int j (m n 1) / 2 - i; auto max_left1 (i 0) ? INT_MIN : nums1[i-1]; auto min_right1 (i m) ? INT_MAX : nums1[i]; auto max_left2 (j 0) ? INT_MIN : nums2[j-1]; auto min_right2 (j n) ? INT_MAX : nums2[j]; if(max_left1 min_right2 max_left2 min_right1) { // 计算中位数... } else if(max_left1 min_right2) { right i - 1; } else { left i 1; } } return 0.0; }5. 高级技巧与性能优化5.1 自定义比较函数STL二分函数支持传入自定义比较器这使得它们能处理复杂数据结构struct Item { int id; string name; double price; }; vectorItem items; // 按price排序后... auto it lower_bound(items.begin(), items.end(), targetPrice, [](const Item a, double price) { return a.price price; });5.2 结合其他算法实现高效查询二分查找常与其他STL算法配合使用。例如在已去重的有序容器中检查是否存在某元素bool exists binary_search(v.begin(), v.end(), value); // 等效于 bool exists lower_bound(v.begin(), v.end(), value) ! v.end() *lower_bound(v.begin(), v.end(), value) value;5.3 容器选择对性能的影响不同容器使用二分查找的性能差异容器类型随机访问内存连续性适合二分查找vectorO(1)是★★★★★dequeO(1)部分★★★★☆arrayO(1)是★★★★★listO(n)否不推荐6. 常见陷阱与调试技巧即使使用STL函数二分查找仍可能出错。以下是典型问题及解决方案问题一未排序的输入容器症状返回结果不可预测检查assert(is_sorted(v.begin(), v.end()))问题二错误的下标转换错误示例int index lower_bound(...) - v.begin() 1;正确做法明确理解迭代器算术的含义问题三自定义比较函数不一致规则比较函数必须与排序时使用的保持一致调试验证is_sorted使用相同比较器实际项目中我习惯在复杂二分查找前添加验证断言assert(is_sorted(v.begin(), v.end())); auto it lower_bound(v.begin(), v.end(), target); if(it ! v.end()) { // 处理找到的情况 }7. 扩展到其他编程语言的实现虽然本文聚焦C但二分查找的思想是通用的。其他语言中的等效实现Python:import bisect first bisect.bisect_left(arr, target) last bisect.bisect_right(arr, target) - 1Java:int first Arrays.binarySearch(arr, target); if(first 0) { // 处理找到的情况 }JavaScript:// 自定义实现 function lowerBound(arr, target) { let low 0, high arr.length; while(low high) { const mid Math.floor((low high)/2); arr[mid] target ? low mid 1 : high mid; } return low; }