std::lower_bound返回第一个≥target的迭代器，不保证相等；std::upper_bound返回第一个>target的迭代器；二者配合可得等于target的区间，要求容器有序且比较逻辑一致。
std::lower_bound 返回的是第一个 ≥ target 的迭代器
它不保证元素等于 target，只保证“不小于”。如果所有元素都小于 target，返回 end()；如果 target 存在，它指向最左边那个等于 target 的位置；如果不存在，指向第一个比 target 大的位置。
常见错误是以为它“找相等”，结果在 if (*it == target) 前没检查 it != container.end()，导致解引用 end() 迭代器——UB（未定义行为）。
- 使用场景：去重插入、查找左边界、计算某个值的出现起始位置
- 容器必须有序（升序），且比较逻辑和排序一致（比如用
greater<int></int>排序，就得传对应comp） - 时间复杂度是 O(log n)，但底层依赖随机访问迭代器；对
std::list用它，性能退化成 O(n)（因为std::advance慢）
std::upper_bound 返回的是第一个 > target 的迭代器
它跳过所有等于 target 的元素，直接指向“严格大于”的第一个位置。和 lower_bound 配合，[lower_bound, upper_bound) 就是所有等于 target 的连续区间（如果存在）。
容易踩的坑是误以为 upper_bound - lower_bound 总能算出频次——这仅对支持随机访问的容器（如 std::vector、std::array）成立；对 std::set，得用 std::distance，而且是线性时间。
立即学习“C++免费学习笔记（深入）”；
- 参数
comp必须和容器排序所用的一致，否则行为未定义 - 如果 target 大于等于所有元素，同样返回
end() - 对
std::set/std::map，这两个函数内部走红黑树路径，仍是 O(log n)，无需担心
为什么两个函数都返回迭代器而不是 bool 或索引？
因为 C++ 算法设计哲学是“操作迭代器”，不是“操作数据”。返回迭代器让你能无缝衔接插入、擦除、构造子范围等操作，比如：vec.insert(lower_bound(vec.begin(), vec.end(), x), x) 直接保持有序。
用索引反而多此一举：需要额外存 begin()，还要处理不同容器的索引类型（size_t vs ptrdiff_t），且不通用。
- 不要自己写
it - vec.begin()转索引，除非真需要下标运算 - 不要对
std::forward_list用这两个函数——它不支持双向遍历，根本没法二分 - 自定义类型必须提供可比较的
operator<或传入合法comp，否则编译失败，错误信息通常很长，关键看有没有invalid operands to binary expression
一个典型误用：在无序容器上调用
比如对刚 push_back 完的 std::vector 直接调 lower_bound，结果不可预测——算法不检查是否有序，它只是按升序语义一路折半，最终可能返回任意位置。
调试时现象往往是：偶尔对得上，换数据就错；或者返回 end() 即使 target 明明存在。
- 确保调用前已调用
std::sort（或初始化时就有序） - 如果频繁插入又查询，考虑换
std::set，它自动维持有序，find也是 O(log n) - 用
assert(std::is_sorted(v.begin(), v.end()))在 debug 版本里兜底（注意：C++20 才有std::is_sorted，旧标准需手写或用<algorithm>里的等价写法）
实际写的时候，最容易被忽略的是：两个函数对“相等”的定义完全依赖你传的比较逻辑，而不是 == 操作符。哪怕 a == b 为真，只要 comp(a, b) 和 comp(b, a) 都为假，它们就被视为“等价”，lower_bound 就可能停在其中任意一个上。
