std::upper_bound返回指向第一个大于n的元素的迭代器，要求序列升序；需解引用取值、减begin()得下标；若无满足元素则返回end()，使用前须检查；适用于vector、array及裸指针数组。
用 std::upper_bound 最省事，但得懂它返回什么
它直接返回指向「第一个大于 N」的元素的迭代器，前提是数组已升序排列。别误以为它返回下标或值——它返回指针（或迭代器），要取值得解引用，要算位置得减开头。
- 如果整个数组都不大于
N，它返回end()，用前必须检查，否则解引用会崩 - 如果数组是
std::vector，it - vec.begin()才是下标；C 风格数组则用it - arr - 它对
std::array、std::vector、裸指针数组都适用，底层只依赖随机访问迭代器
手写二分时，left 和 right 边界怎么设才不越界
常见错误是把 right 初始化成 size 或 size - 1 搞混，导致漏查末尾或访问越界。统一用左闭右开区间 [left, right) 最稳：初始 left = 0, right = size，循环条件为 left ，更新时 <code>right = mid（不是 mid - 1）。
- 每次收缩后区间仍保持「答案一定在 [left, right) 内」的不变性
- 退出时
left == right，就是第一个大于N的下标；若等于size，说明没找到 - 别用
(left + right) / 2算mid，大数组可能溢出，改用left + (right - left) / 2
std::upper_bound 和手写二分性能差多少？
几乎没差别。标准库实现就是优化过的二分，且做了分支预测和指令级优化。除非你用的是极老编译器或禁用了优化，否则不用纠结“自己写更快”。真正影响性能的是数据局部性——比如数组太大、cache 不友好，或者比较函数太重（比如字符串比较）。
- 如果比较逻辑复杂（如自定义结构体+多字段判断），把比较函数写成
constexpr或内联，比换算法更有效 - 连续多次查不同
N时，考虑是否能用向量化（如std::lower_bound批量版不存在，别硬凑） - 别为了“看起来快”而用
while循环手动展开二分——现代 CPU 流水线讨厌这种强分支
遇到 std::upper_bound 返回结果不对，先盯这三个地方
不是算法错，大概率是环境没配对。最常踩的坑就三个：
立即学习“C++免费学习笔记（深入）”；
- 数组其实没排序，或排序用的比较规则和
upper_bound不一致（比如排序用std::greater，但查的时候没传相同谓词） - 传了自定义比较函数，但没保证严格弱序（比如
a == b时还返回true），行为未定义 - 用
float或double当键值，又没处理 NaN 或精度问题，upper_bound可能跳过本该命中的位置
浮点数场景下，宁可转成整数倍再查，也别信默认比较。
