在 C++ 里，lower_bound 和 upper_bound 是非常常用的二分查找函数。
它们最重要的作用，不是单纯判断一个数在不在数组里，而是在有序区间中查找边界位置。
很多人刚接触这两个函数时，最容易混淆两点：
- 它们返回的是位置，不是元素值。
- 在升序和降序数组中，它们的含义并不一样，尤其是配合
greater<int>()时更要分清楚。
这篇文章就把这 4 种最常见的写法一次讲明白。
1. 升序数组中的用法
先看一个升序数组：
int num[] = {1, 3, 5, 7, 7, 9};如果我们查找数字 7：
int pos1 = lower_bound(num, num + 6, 7) - num;
int pos2 = upper_bound(num, num + 6, 7) - num;它们分别表示：
lower_bound(num, num + 6, 7)：返回第一个大于或等于 7 的位置upper_bound(num, num + 6, 7)：返回第一个大于 7 的位置
代入这个数组：
pos1 = 3，因为num[3] = 7，这是第一个大于等于7的元素pos2 = 5，因为num[5] = 9，这是第一个大于7的元素
所以在升序数组中：
lower_bound -> 找 >= x 的第一个位置
upper_bound -> 找 > x 的第一个位置2. 降序数组中的用法
如果数组是降序的，就不能直接用默认写法了。
这时要配合比较器 greater<int>()。
例如：
int num[] = {9, 7, 7, 5, 3, 1};查找 7：
int pos3 = lower_bound(num, num + 6, 7, greater<int>()) - num;
int pos4 = upper_bound(num, num + 6, 7, greater<int>()) - num;这时含义会变成：
lower_bound(num, num + 6, 7, greater<int>())：返回第一个小于或等于 7 的位置upper_bound(num, num + 6, 7, greater<int>())：返回第一个小于 7 的位置
放到数组里：
pos3 = 1，因为num[1] = 7，这是第一个小于或等于7的元素pos4 = 3，因为num[3] = 5，这是第一个小于7的元素
所以在降序数组中：
lower_bound + greater<int>() -> 找 <= x 的第一个位置
upper_bound + greater<int>() -> 找 < x 的第一个位置3. 这 4 行代码到底是什么意思
你给的代码可以这样理解：
int pos1=lower_bound(num,num+6,7)-num;
// 返回升序数组中第一个大于或等于 7 的位置
int pos2=upper_bound(num,num+6,7)-num;
// 返回升序数组中第一个大于 7 的位置
int pos3=lower_bound(num,num+6,7,greater<int>())-num;
// 返回降序数组中第一个小于或等于 7 的位置
int pos4=upper_bound(num,num+6,7,greater<int>())-num;
// 返回降序数组中第一个小于 7 的位置注意最后的 - num。
因为 lower_bound 和 upper_bound 返回的是指针或迭代器，减去数组首地址以后，得到的才是我们平时说的“下标位置”。
4. 一张表记住 4 种写法
| 写法 | 数组顺序 | 含义 |
|---|---|---|
lower_bound(begin, end, x) | 升序 | 第一个 >= x 的位置 |
upper_bound(begin, end, x) | 升序 | 第一个 > x 的位置 |
lower_bound(begin, end, x, greater<int>()) | 降序 | 第一个 <= x 的位置 |
upper_bound(begin, end, x, greater<int>()) | 降序 | 第一个 < x 的位置 |
这张表基本就是这道知识点的核心。
5. 使用时最容易踩的坑
5.1 数组必须有序，而且排序方向要匹配
- 默认写法要求区间是升序
- 使用
greater<int>()时，区间必须是降序
如果顺序不对，结果就不可靠。
5.2 返回的是位置，不是元素值
例如：
int pos = lower_bound(num, num + 6, 7) - num;这里的 pos 是位置，不是 7 本身。
如果你想拿到这个位置对应的值，还得再写：
int value = num[pos];当然前提是 pos 没有越界。
5.3 找不到时可能返回尾后位置
例如在升序数组 {1, 3, 5} 中查找 10：
int pos = lower_bound(num, num + 3, 10) - num;这时 pos 会等于 3，也就是区间末尾的后一个位置。
所以实际做题时，拿到结果后通常要判断：
if (pos < n) {
// 位置有效
}6. 总结
lower_bound 和 upper_bound 的本质，都是在有序区间里找边界。
在升序数组中：
lower_bound找第一个>= xupper_bound找第一个> x
在降序数组中，配合 greater<int>()：
lower_bound找第一个<= xupper_bound找第一个< x
只要把这 4 种情况分清楚，STL 二分函数这一块基本就不会再混了。
Comments NOTHING