lower_bound找的是第一个不小于目标值的位置，返回指向第一个满足!(value

lower_bound 找的是“第一个不小于目标值”的位置

它返回指向第一个满足 !(value 的迭代器，也就是 ≥ 目标值的最左位置。常用于有序容器（<code>vector、array、set）中做二分查找，比手写循环快且不易出错。

常见错误是误以为它找“等于”，结果在目标不存在时仍返回合法迭代器——比如 lower_bound(v.begin(), v.end(), 5) 在 v = {1,3,7,9} 中返回指向 7 的迭代器，不是 end()。

• 必须保证区间已升序排列（默认用 比较），否则行为未定义
• 若想自定义比较逻辑（如降序或结构体字段），需传入第 4 个参数，如 greater<int>()</int> 或 lambda
• 对 vector 使用时，返回的是随机访问迭代器，支持 - 运算求下标：lower_bound(v.begin(), v.end(), x) - v.begin()

upper_bound 找的是“第一个大于目标值”的位置

它返回指向第一个满足 value 的迭代器，即 > 目标值的最左位置。和 <code>lower_bound 配合，能快速确定某个值在有序序列中的出现范围。

典型误用：用 upper_bound 判断存在性——它不关心“等不等于”，只管“大不大”。例如 v = {2,2,2,5,5}，查 2 时 lower_bound 指向首 2，upper_bound 指向首个 5，二者差值就是 2 的出现次数。

立即学习“C++免费学习笔记（深入）”；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

• 与 lower_bound 一样，依赖有序性；比较函数必须和排序时一致
• 若容器是 set/multiset，直接调用成员函数更高效：s.lower_bound(x)，避免传入 begin()/end()
• 对重复元素，[lower_bound, upper_bound) 是左闭右开的完整匹配区间

pair 包装两个函数可一次性拿到范围

STL 提供 equal_range，内部就是调用 lower_bound 和 upper_bound，返回 pair。适合需要完整定位所有匹配项的场景，比如去重统计或批量删除。

性能上，它比分别调两次略优（尤其对 set 等非随机访问容器），但对 vector 差异不大。别为了“看起来简洁”而牺牲可读性——如果只用到下界，就别硬套 equal_range。

• 返回类型是 pair<it it></it>，可用结构化绑定（C++17）：auto [l, r] = equal_range(v.begin(), v.end(), x);
• 检查是否找到：判断 l != r，而非 l != v.end()（因为即使没找到，l 和 r 也可能相等且非 end）
• 注意：equal_range 的比较逻辑也必须和排序一致，不能混用 less 和 greater

在 std::map / std::multimap 中别乱用全局函数

这些关联容器自带 lower_bound、upper_bound 和 equal_range 成员函数，它们按 key 排序，且对红黑树结构做了优化。用全局版本（std::lower_bound）会退化成 O(n)，因为无法利用树的层级跳转。

另一个坑是键类型不支持默认比较：比如自定义类作 key 时，忘了提供 operator 或传 <code>Compare 模板参数，编译会报错，错误信息常含 invalid operands to binary expression。

• 正确写法：m.lower_bound(key)，不是 std::lower_bound(m.begin(), m.end(), key)
• map 中 lower_bound 找不到时返回 m.end()；multimap 同理，但可能有多个相同 key
• 插入新元素后，原有迭代器不一定失效，但 lower_bound 结果需重新查——map 不保证插入不扰动已有节点位置逻辑

实际用的时候，先确认容器类型和有序性，再决定调成员函数还是算法。边界判断宁可多写一行 != end()，也别靠直觉猜返回值。