二分查找进阶：深入理解lower_bound与upper_bound的边界与使用技巧-北京尧图网络

1. 为什么二分查找不是找到就停需求先行的两个变种很多人第一次接触二分查找学的是在有序数组里找一个目标值找到了返回下标找不到返回-1。这个版本没有错但它只覆盖了二分查找最基础的一种用法。等真正写业务代码、刷算法题、处理数据时你会发现大部分需求根本不是找某个确切值而是找该插入的位置找第一个比它大的数找最后一个比它小的数这类边界查询。这时候lower_bound和upper_bound两个变种就派上用场了。从名字上也能看出设计意图lower_bound找的是下界——第一个不小于目标值的位置upper_bound找的是上界——第一个大于目标值的位置。这也是它们的英文原意lower bound 和 upper bound。C 的 STL 里直接提供了这两个现成函数C#、Java、Python 等语言也都有等价实现Java 里的ceilingEntry、Python 里的bisect_left/bisect_right本质就是这两兄弟。这俩函数处理的场景一句话概括就是数组里可能存在重复元素也可能不存在目标值但我们需要的是一个明确的位置而不是有没有。比如你有一份成绩单学生分数按升序排列。你想知道有多少人分数大于等于60用lower_bound找到第一个大于等于60的下标然后用数组长度减去它就得出人数。你想知道有多少人分数大于60就用upper_bound找第一个大于60的下标。如果没有这两个函数你得自己判断边界、处理重复值写出来的代码又长又容易错。我把核心区别用最简单的方式记下来lower_bound返回第一个 target的元素位置upper_bound返回第一个 target的元素位置注意这两个函数的前提都是数组有序。你可以用升序数组也可以自定义比较规则。升序情况下lower_bound和upper_bound返回的位置差恰好等于目标值在数组中出现的次数。这个性质特别有用后面我会专门拿一节来聊。提示如果你遇到的是降序数组不能直接调这两个函数。需要用自定义比较器把降序调整成升序语义或者先翻转思路对降序数组求第一个小于等于目标值的位置实际上等价于对升序后的数组求lower_bound。这一点极其容易踩坑我在第5节详细说。读到这里你可能会问道理我懂了但我在实际代码里到底拿它返回的是下标还是值它能直接用在哪些业务场景里别急下面一节我把 C 的实现细节和调用方式讲透然后再展开说应用场景。2. 从库函数到手写模板底层逻辑决定了你的代码怎么写2.1 STL 的原生 API 与迭代器语义先看 C 的标准接口。这两个函数定义在algorithm头文件里templateclass ForwardIt, class T ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T value); templateclass ForwardIt, class T, class Compare ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T value, Compare comp); templateclass ForwardIt, class T ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T value); templateclass ForwardIt, class T, class Compare ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T value, Compare comp);返回值是迭代器ForwardIt不是下标。如果你要拿下标写法是vectorint nums {1, 3, 5, 7, 9}; auto it lower_bound(nums.begin(), nums.end(), 5); int index it - nums.begin(); // 迭代器相减得到下标很多人初次接触时会被迭代器绕晕其实理解起来不难it - begin得到的整数就是该元素在数组中的下标如果it end()说明整个数组里没有满足条件的元素此时it - begin nums.size()。这里有个重要细节注意和find的返回值区分。find返回迭代器找不到时返回end()你以为下标是 -1其实是在心里做了转换。而lower_bound/upper_bound在找不到时返回的也是end()这并不代表没地方放恰恰相反它代表的是目标值应该插入到数组末尾。这一层语义非常关键我见过不少人在这一步栽跟头把end()当成失败其实它表示所有元素都比目标值小插入位置在最后。2.2 手写模板考试和面试要的那20行代码虽然 STL 现成可用但笔试、面试、考研、计算机等级考试里往往被要求手写。更重要的是只有理解了手写版本你对库函数的边界行为才会真正有感觉。一个正确的lower_bound写法长这样int lowerBound(const vectorint arr, int target) { int left 0, right arr.size(); // 注意 right 初始化为 n不是 n-1 while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // arr[mid] 小于 target说明 mid 及其左边都不可能是答案 } else { right mid; // arr[mid] targetmid 可能是答案继续向左压缩 } } return left; // 最终 left right指向第一个 target 的位置 }对应upper_boundint upperBound(const vectorint arr, int target) { int left 0, right arr.size(); while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // arr[mid] target说明 mid 及其左边都不可能是答案 } else { right mid; // arr[mid] targetmid 可能是答案继续向左压缩 } } return left; }这个模板的奥妙全在两点第一循环条件是left right不是left right。因为区间定义是左闭右开[left, right)退出时left right这个位置就是答案。如果把right初始化为n-1用闭区间写判断逻辑会变得复杂容易在mid和mid1之间反复摇摆。第二mid的收缩方向决定了找的是下界还是上界。lower_bound中arr[mid] target时left mid 1而arr[mid] target时right mid这保证了right永远指向一个可能成为答案的位置不会跳过。upper_bound只是把判断从改成了一行之差结果就从大于等于变成了大于。为什么要用left (right - left) / 2而不是(left right) / 2直接相加在极端情况下可能整数溢出虽然你处理的数据规模未必有那么大但写成这种形式是一个好习惯面试时也更容易解释清楚。2.3 我自己做一个小测试验证边界光看代码还不够我习惯把边界情况跑一遍心里才踏实。用一个简单的测试数组arr {1, 2, 2, 2, 4, 6}目标值lower_bound 返回下标下标处的值upper_bound 返回下标下标处的值21244344440010176end6end44456这个表格很有信息量。注意两行目标值 3 不在数组里但lower_bound和upper_bound返回同一个下标 4也就是 4 所在的位置这说明第一个大于等于3和第一个大于3在数组里都没有3的情况下是同一个位置。目标值 7 超出了数组最大值两个函数都返回 6即end()对应的下标此时如果要插入就应该插在最后。这个测试直接告诉我遇到重复元素时lower_bound和upper_bound的下标差就是重复次数。target2时upper_bound(4) - lower_bound(1) 3正好是 2 出现的次数。提示不要只记结论建议你自己在本地跑一次这段代码把mid的变化过程打印出来你会对二分查找的收敛过程产生肌肉记忆。3. 二元组组合拳用 lower_bound 和 upper_bound 求目标值的出现区间3.1 为什么不是找一个值而是找一个区间很多算法教材里有一道经典题在有序数组中查找目标值的起始位置和结束位置即[first, last]。这道题如果只靠找到一个目标值下标再向两边扩散来解在重复元素很多、数组很长的情况下最坏复杂度会退化成 O(n)失去二分查找的意义。正确的思路就是两个函数各用一次vectorint searchRange(vectorint nums, int target) { if (nums.empty()) return {-1, -1}; int left lower_bound(nums.begin(), nums.end(), target) - nums.begin(); int right upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1; if (left right) return {-1, -1}; // 目标值不存在 return {left, right}; }left是第一个等于 target 的下标right是最后一个等于 target 的下标。如果 target 不存在left会指向第一个大于 target 的元素此时right left - 1left right判断成立直接返回 {-1, -1}。这套组合拳的时间复杂度是两个 O(log n)合计 O(log n)比啥都强。代码里的细节也值得念叨如果数组为空先做一次空判断避免lower_bound对空迭代器调用时产生未定义行为虽然有些实现能兜住但自己先判断更稳。求right时upper_bound返回的是第一个大于 target的位置减 1 才是最后一个等于 target 的位置这个 -1 是必写的。这题常出现在各种笔试里思路通了之后代码几乎可以背下来。不过我更建议你理解为什么left和right要这样算而不是背模板。3.2 统计区间内元素数量count 的另一种实现再往深一层如果你只是想统计某个值出现的次数不需要下标那直接int count upper_bound(nums.begin(), nums.end(), value) - lower_bound(nums.begin(), nums.end(), value);# Python 里的等价写法 import bisect count bisect.bisect_right(nums, value) - bisect.bisect_left(nums, value)这种写法的好处是直白且不易出错。虽然 STL 里也有count算法但那个算法是遍历式线性复杂度在有序数组上反而浪费了排序的优势。当数组很大、查询很频繁时二分式的 count 明显更优。实际工程里这种区间长度的写法最常用于数值分段统计。举个例子你有一个用户年龄列表想统计各年龄段的人数[0,18)、[18,30)、[30,45)、[45,60)、[60,)。用lower_bound和upper_bound分别对每个分界点查询用差值就能得到每个年龄段数量代码写出来非常清爽vectorint ages {15, 22, 18, 45, 60, 30, 28, 35, 12, 55}; sort(ages.begin(), ages.end()); auto countInRange [](int low, int high) { // [low, high) 区间low和high是年龄阈值 return upper_bound(ages.begin(), ages.end(), high) - lower_bound(ages.begin(), ages.end(), low); }; cout 18岁以下人数: countInRange(0, 18) endl;注意我用的是[low, high)半开区间这种表示法在区间统计里特别自然也符合 STL 一贯的[first, last)风格。写惯了之后你会爱上半开区间的。3.3 实际项目里的应用区间重叠判断再说一个更工程化的例子。假设你有一个预订系统的订单列表每个订单有开始时间和结束时间时间戳数组按开始时间排序。现在要判断给定一个时间点 t有没有正在进行的订单等价于找最后一个开始时间 t 的订单再看它的结束时间是否 t。这可以拆成upper_bound变体。不过这里有一个坑upper_bound找的是第一个大于目标值的位置因此最后一个 t 的位置是upper_bound(开始时间, t) - 1。然后取这个订单的结束时间判断即可。很多人会掉进想找一个lower_bound_leq函数的误区以为 C 没有提供就只能自己写。其实稍微做个转换就出来了最后一个 target的位置 lower_bound(target) - 1最后一个 target的位置 upper_bound(target) - 1这两个转换非常有用建议背下来。面试时如果能把这种库函数组合讲清楚比手写一个循环更有说服力。4. 实际业务中的三个常见场景插入位置、最近值查找、数据分桶4.1 维护有序集合时的插入位置前面提到过lower_bound/upper_bound本质上回答的是新元素应该插在哪。在动态维护有序数组时这个需求非常频繁。比如你有一个有序的排行榜分数列表来了一个新分数你要把新分数插到正确位置同时不破坏有序性vectorint scores {100, 95, 90, 85, 80}; // 注意降序数组不能直接用 lower_bound先转成升序语义 // 方法使用 greaterint() 比较器 auto it lower_bound(scores.begin(), scores.end(), 88, greaterint()); scores.insert(it, 88);这里用greaterint()自定义比较器后lower_bound在降序数组中的语义变成了第一个目标值的位置正好满足降序插入的需求。这个例子可能让你有点晕别急着背。降序数组的适配是整个系列里最容易蒙圈的地方我会在第5节专门用一个独立小节彻底讲透。先记住结论在使用自定义比较器时lower_bound找的是第一个令比较器返回 false 的位置。4.2 查找最接近目标值的元素在实际算法题中经常遇到在有序数组中找到最接近 target 的元素。传统做法是二分找到插入点然后比较它和它前一个元素的距离谁近取谁。用lower_bound写就是int findClosest(vectorint arr, int target) { int pos lower_bound(arr.begin(), arr.end(), target) - arr.begin(); if (pos 0) return arr[0]; if (pos arr.size()) return arr.back(); // 比较 pos 和 pos-1 哪个更接近 return (arr[pos] - target target - arr[pos - 1]) ? arr[pos] : arr[pos - 1]; }思路一句话lower_bound给出第一个 target 的位置那么不大于 target 的最大元素就在pos - 1两个候选与 target 的距离比一下即可。这个思路也常出现在二分答案、搜索旋转数组等进阶题目里。再进一步如果数组元素可能是浮点数比较距离时记得用fabs并且注意浮点数精度误差必要时用一个极小 epsilon 做相等判断。4.3 数据分桶与直方图构建在数据分析场景里分桶统计非常常见。你有大量测量数据比如点击量、响应时间、价格希望把它们划分到若干区间里然后统计每桶的数量。此时没有现成的区间查询APIlower_bound/upper_bound就是你的两手工具。假设分桶边界是bounds {0, 10, 20, 30, 40, 50}边界含义是[0,10) [10,20) ... [40,50)那么对任意一个数据点 x它属于哪个桶可以这样写int bucketIndex upper_bound(bounds.begin(), bounds.end(), x) - bounds.begin() - 1;原理是upper_bound返回第一个 x 的边界往前一个桶就是 x 所在的桶。如果 x 正好等于某个边界值比如 x10upper_bound返回的是边界 20 的位置减一落在桶1即[10,20)和半开区间的定义吻合。这个技巧在写统计脚本、做性能分析报表时特别实用。配合map或unordered_map一次遍历就能完成全量分桶统计代码不超过十行。5. 容易踩的坑降序数组、自定义比较器、float 精度与空容器5.1 降序数组到底怎么用 lower_bound这是使用这两个函数时最大的坑没有之一。STL 对lower_bound的默认行为建立在升序数组上它假定序列是按照比较升序排列的。直接对一个降序数组调用默认版本的lower_bound结果是未定义行为也就是结果完全不可预测可能返回正确也可能返回乱七八糟的迭代器。好在这个问题有官方解法传入自定义比较器。在 C 里标准库规定lower_bound的语义是返回第一个不满足comp(value, *it)为真的迭代器。对于升序默认less等价于第一个*it value的位置。对于降序数组我们希望的是第一个 value的位置也就是第一个*it value不成立的位置那么比较器应该写成greaterint()。写一个通用的小工具函数避免每次手写比较器时搞混方向// 在任意有序容器中查找插入位置order 为 true 表示升序 template typename T, typename Container size_t lowerBoundInEitherOrder(const Container c, const T value, bool ascending) { if (ascending) { return lower_bound(c.begin(), c.end(), value) - c.begin(); } else { return lower_bound(c.begin(), c.end(), value, greaterT()) - c.begin(); } }不过我更推荐的思路是数据进容器之前就先想清楚排序方向。工程上绝大多数有序容器都是升序如果你发现自己要处理降序数组先确认一下能不能在源头把它 reverse 成升序很多时候能省掉后面一堆麻烦。5.2 自定义结构体比较器的正确姿势实际场景中数组元素往往不是纯数字而是一个结构体。比如按商品的价格ID排序。这时自定义比较器就要特别小心STL 要求比较器必须是严格弱序strict weak ordering也就是说它必须满足非自反、反对称、传递性。最简单实用的写法是用std::tie按多个字段做字典序比较。来看一个典型的按价格升序、价格相同时按 ID 升序的结构体数组找到第一个价格 target 的商品struct Item { int price; int id; }; // 排序比较器 auto cmp [](const Item a, const Item b) { return std::tie(a.price, a.id) std::tie(b.price, b.id); }; // lower_bound 用的二元比较器也可以复用 cmp auto it lower_bound(items.begin(), items.end(), targetItem, cmp);注意lower_bound传给比较器的第三个参数targetItem的类型必须能和Item比较。如果只想按价格查找你需要构造一个targetItem{targetPrice, 任意id}然后利用std::tie的字典序特性保证价格相等时任意 id 都不会影响查找结果——只要 target 的 id 设为最小值即可。这里有个更隐蔽的坑如果你只按 price 一个字段排序不排 id然后想用 lower_bound 只按 price 查找你必须让比较器只比较 price而不能比较 id。否则顺序和比较器不一致结果就会错乱。简单说lower_bound 的比较器必须和排序时使用的比较器保持完全一致。5.3 浮点数数组查找时别忽略精度误差浮点数比较是另一个经典陷阱。假设你有一个vectordouble存储温度测量值想找到第一个大于等于 36.5 的位置vectordouble temps {36.1, 36.4, 36.4, 36.6, 37.0}; auto it lower_bound(temps.begin(), temps.end(), 36.5);很多情况下这没问题但浮点数在二进制表示里可能存在误差。比如 0.1 0.2 在 double 里并不精确等于 0.3 的二进制表示你存进去的值和查询用的值可能在边缘处产生微小偏差导致lower_bound的判定和你预期不一致。解决方式有两种存储时使用定点数例如整数存储毫摄氏度比较时引入 epsilon写一个自定义比较器在a b时判断a b - eps。double eps 1e-9; auto floatLess [eps](double a, double b) { return a b - eps; }; auto it lower_bound(temps.begin(), temps.end(), 36.5, floatLess);虽然这个解法不算完美epsilon 取值本身也是门学问但至少比直接裸比较稳妥。一般来说在金融、计量这类对精度敏感的领域直接用整数存分或者毫是更推荐的做法能从根本上绕开浮点问题。5.4 空容器与 end 迭代器的语义最后说一个看着简单但总有人犯迷糊的点对空容器调用lower_bound/upper_bound会直接返回end()。这本身不算错误但如果你紧接着写*it取元素就是解引用空迭代器程序直接崩溃。正确的处理模式是先判断返回值是否等于end()再做下一步。更优雅的方式是配合std::distance获取下标并和下界/上界做比较if (it v.end()) { // 处理找不到的情况 } else { // 安全使用 *it }这个习惯无论是对待二分函数还是对待任何返回迭代器的 STL 算法都是一致适用的。养成这个条件反射能帮你避免大量悬空迭代器相关的 bug。6. 快速记忆一张表一个口诀彻底告别边写边查写到最后我把自己多年用下来觉得最顺手的总结方式分享出来。很多时候我们不是不理解原理而是面对七八种边界情况时大脑容易短路。记这张表和这个口诀基本能解决 90% 的问题。需求函数返回值语义示例arr {1,2,2,2,4,6}target2第一个 targetlower_bound指向第一个不小于 target 的元素返回 index1第一个 targetupper_bound指向第一个大于 target 的元素返回 index4最后一个 targetupper_bound - 1返回 index3最后一个 targetlower_bound - 1返回 index0target 出现次数upper_bound - lower_bound返回 3target 是否存在upper_bound - lower_bound 0返回 true所有元素都 targetlower_bound / upper_bound 都返回 end()对应下标为 size口诀是找下界用 lt找上界用 le差一记得减。拆开解释就是求第一个 x的位置lower_bound求第一个 x的位置upper_bound想得到最后一个 x或最后一个 x先把上面的结果算出来再减一用多了自然会发现这两个函数在 STL 里就是一对黄金搭档左开右闭的区间语义贯穿始终。写代码时把目标值 x 落在哪个区间想清楚代码基本不会出错。最后给一个我自己写代码时的小习惯如果数组里存的是自定义对象、可比较的元组或者任何比较规则复杂的东西我都不会直接裸调lower_bound而是先定义一个语义清晰的比较器并加上注释说明排序规则。这样别人 review 代码时一眼能看懂三个月后我自己回来看也不用重新推导方向。这个习惯帮我少踩了无数个隐蔽的坑今天一并分享给你。

二分查找进阶：深入理解lower_bound与upper_bound的边界与使用技巧

相关推荐

基于MATLAB的多特征融合火灾检测系统GUI实现

模型卡与系统卡：从 Hugging Face 模板到 AI Act 证据链（Annex IV 差距审计）

VL53L4CD ToF测距传感器结合CircuitPython：从参数配置到多传感器实战

更多资讯

红外可见光高光谱SAR图像合集拆包与多模态融合预处理实战

基于PyTorch LSTM的电价预测实战：未来24小时曲线构建解析

阿里云K8s部署Vue2+SpringBoot2.5+Nacos2.0.3全流程

K8s 部署 Vue2 + Spring Boot 2.5 + Nacos 2.0.3 实战清单与避坑指南

贝叶斯优化调参实战：高斯过程与采集函数原理及Python实现

射影几何核心概念详解：齐次坐标、交比与极点极线

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？