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>头文件里：

template<class ForwardIt, class T> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value); template<class ForwardIt, class T, class Compare> ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp); template<class ForwardIt, class T> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value); template<class ForwardIt, class T, class Compare> ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp);

返回值是迭代器（ForwardIt），不是下标。如果你要拿下标，写法是：

vector<int> 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 vector<int>& 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] >= target，mid 可能是答案，继续向左压缩 } } return left; // 最终 left == right，指向第一个 >= target 的位置 }

对应upper_bound：

int upperBound(const vector<int>& 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] > target，mid 可能是答案，继续向左压缩 } } return left; }

这个模板的奥妙全在两点：

第一，循环条件是left < right，不是left <= right。因为区间定义是左闭右开[left, right)，退出时left == right，这个位置就是答案。如果把right初始化为n-1，用闭区间写，判断逻辑会变得复杂，容易在mid和mid+1之间反复摇摆。

第二，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}：

这个表格很有信息量。注意两行：

• 目标值 3 不在数组里，但lower_bound和upper_bound返回同一个下标 4，也就是 4 所在的位置，这说明"第一个大于等于3"和"第一个大于3"在数组里都没有3的情况下是同一个位置。
• 目标值 7 超出了数组最大值，两个函数都返回 6（即end()对应的下标），此时如果要插入，就应该插在最后。

这个测试直接告诉我：遇到重复元素时，lower_bound和upper_bound的下标差就是重复次数。target=2时，upper_bound(4) - lower_bound(1) = 3，正好是 2 出现的次数。

提示：不要只记结论，建议你自己在本地跑一次这段代码，把mid的变化过程打印出来，你会对二分查找的收敛过程产生肌肉记忆。

3. 二元组组合拳：用 lower_bound 和 upper_bound 求"目标值的出现区间"

3.1 为什么不是"找一个值，而是找一个区间"

很多算法教材里有一道经典题：在有序数组中查找目标值的起始位置和结束位置，即[first, last]。这道题如果只靠"找到一个目标值下标再向两边扩散"来解，在重复元素很多、数组很长的情况下，最坏复杂度会退化成 O(n)，失去二分查找的意义。

正确的思路就是两个函数各用一次：

vector<int> searchRange(vector<int>& 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 - 1，left > 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分别对每个分界点查询，用差值就能得到每个年龄段数量，代码写出来非常清爽：

vector<int> 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本质上回答的是"新元素应该插在哪"。在动态维护有序数组时，这个需求非常频繁。比如你有一个有序的排行榜分数列表，来了一个新分数，你要把新分数插到正确位置，同时不破坏有序性：

vector<int> scores = {100, 95, 90, 85, 80}; // 注意：降序数组不能直接用 lower_bound，先转成升序语义 // 方法：使用 greater<int>() 比较器 auto it = lower_bound(scores.begin(), scores.end(), 88, greater<int>()); scores.insert(it, 88);

这里用greater<int>()自定义比较器后，lower_bound在降序数组中的语义变成了"第一个 <= 目标值的位置"，正好满足降序插入的需求。

这个例子可能让你有点晕，别急着背。降序数组的适配是整个系列里最容易蒙圈的地方，我会在第5节专门用一个独立小节彻底讲透。先记住结论：在使用自定义比较器时，lower_bound找的是"第一个令比较器返回 false 的位置"。

4.2 查找"最接近目标值"的元素

在实际算法题中，经常遇到"在有序数组中找到最接近 target 的元素"。传统做法是二分找到插入点，然后比较它和它前一个元素的距离，谁近取谁。用lower_bound写就是：

int findClosest(vector<int>& 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 数据分桶与直方图构建

在数据分析场景里，分桶统计非常常见。你有大量测量数据（比如点击量、响应时间、价格），希望把它们划分到若干区间里，然后统计每桶的数量。此时没有现成的"区间查询"API，lower_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 正好等于某个边界值，比如 x=10，upper_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不成立的位置，那么比较器应该写成greater<int>()。

写一个通用的小工具函数，避免每次手写比较器时搞混方向：

// 在任意有序容器中查找插入位置，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, greater<T>()) - 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 浮点数数组查找时别忽略精度误差

浮点数比较是另一个经典陷阱。假设你有一个vector<double>存储温度测量值，想找到第一个大于等于 36.5 的位置：

vector<double> 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% 的问题。

口诀是："找下界用 lt，找上界用 le，差一记得减"。拆开解释就是：

• 求"第一个 >= x"的位置：lower_bound
• 求"第一个 > x"的位置：upper_bound
• 想得到"最后一个 <= x"或"最后一个 < x"，先把上面的结果算出来，再减一

用多了自然会发现，这两个函数在 STL 里就是一对黄金搭档，左开右闭的区间语义贯穿始终。写代码时把"目标值 x 落在哪个区间"想清楚，代码基本不会出错。

最后给一个我自己写代码时的小习惯：如果数组里存的是自定义对象、可比较的元组，或者任何"比较规则复杂"的东西，我都不会直接裸调lower_bound，而是先定义一个语义清晰的比较器，并加上注释说明排序规则。这样别人 review 代码时一眼能看懂，三个月后我自己回来看，也不用重新推导方向。这个习惯帮我少踩了无数个隐蔽的坑，今天一并分享给你。