std::upper_bound查找第一个严格大于目标值的迭代器，要求容器升序排列或配合对应比较函数（如降序时用std::greater），时间复杂度o(log n)，需随机访问迭代器，返回end()时须判空避免解引用崩溃。
std::upper_bound 查找的是严格大于目标的第一个位置
它不找“大于等于”，也不找“第一个等于”，而是精确匹配“第一个 > target 的迭代器”。这是它和 std::lower_bound 的本质区别：后者找的是第一个 ≥ target 的位置。
必须确保容器已升序排列（默认比较），否则行为未定义。如果你用自定义比较函数，要保证其满足严格弱序（strict weak ordering）——比如不能写 a ，得用 <code>a 。
返回值是迭代器，可能等于 end()，务必检查：
auto it = std::upper_bound(v.begin(), v.end(), x);
if (it != v.end()) {
// *it 就是第一个大于 x 的元素
}
常见错误：把 upper_bound 当成 “找插入位置” 却忽略语义
很多人以为 std::upper_bound 是“为 x 找上界插入点”，这没错，但容易混淆插入后是否允许重复。它实际插入的位置，会让所有 ≤ x 的元素都在它左边，x 本身（如果存在）也一定在它左边——所以插入后，x 不会出现在该位置或其右侧，重复的 x 全被甩在左侧。
- 若容器含多个
x，upper_bound返回最后一个x的下一个位置 - 若容器不含
x，它等价于lower_bound（因为第一个 > x 就是第一个 ≥ x） - 误用
std::greater<int>()</int>时，必须同步传给upper_bound，否则逻辑翻车
降序容器怎么用 upper_bound 找“大于 target 的第一个”？
在降序排列的容器里，“大于 target 的第一个”其实是靠左的、数值更大的那个，而默认 upper_bound 假设升序，直接用会出错。
正确做法是显式传入 std::greater<int>()</int>（或其他对应类型）：
std::vector<int> v = {10, 8, 6, 4, 2}; // 降序
auto it = std::upper_bound(v.begin(), v.end(), 5, std::greater<int>());
// 返回指向 4 的迭代器 —— 因为 4 是第一个 下 a > b 意味着“a 在逻辑顺序中排在 b 前面”
// 所以 upper_bound 找的是第一个“不满足 comp(value, target)”的位置
// 即第一个使得 !(value > target) 成立的位置 → 第一个 value target”，应该用 lower_bound + greater</int></int>
结论：在降序容器中找“第一个 > target”，应使用 std::lower_bound(v.begin(), v.end(), target, std::greater<int>())</int>；而 upper_bound + greater 实际找的是第一个 ≤ target 的位置。这点极易搞反。
性能与边界：它不遍历，但依赖随机访问迭代器
std::upper_bound 是二分查找，时间复杂度 O(log n)，但要求迭代器支持 operator+ 和减法（即 RandomAccessIterator）。对 std::list 或 std::forward_list 不能直接用——得换 std::upper_bound 的非标准替代（如手写线性扫描），或者改用 std::set/std::map 的成员函数 upper_bound，它们是 O(log n) 且不要求随机访问。
另外注意：浮点数比较慎用默认 upper_bound，尤其当目标值由计算产生时，可能因精度误差导致找不到预期位置。必要时应配合 std::nextafter 或自定义带 epsilon 的比较谓词。
最常被忽略的一点：返回的迭代器合法 ≠ 容器非空。哪怕 v.empty()，v.begin() == v.end()，此时调用 upper_bound 仍返回 v.end()，解引用前不检查就会崩溃。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
