std::lower_bound比手写二分更可靠，因其内部已严谨处理越界、死循环、边界遗漏等问题，并针对随机访问迭代器优化；它返回第一个≥目标值的迭代器，精准对应下界定义。
std::lower_bound 为什么比手写二分更可靠
手写二分容易越界、死循环、漏边界，std::lower_bound 内部已处理所有边界条件，且对随机访问迭代器（如 vector、array）做了优化。它不返回布尔值，而是返回第一个 ≥ 目标值的迭代器，这正是「下界」定义——避免你反复纠结 left 还是 <code>left 。
常见错误现象：std::binary_search 只返回 bool，查不到位置；手写时用 int mid = (l + r) / 2 在大索引下溢出；忘记检查 it != vec.end() 就解引用。
- 使用场景：查找插入位置、去重后统计频次、求最长非降子序列中的替换点
- 参数差异：
std::lower_bound(first, last, val)要求[first, last)已排序；val类型需能与元素比较（支持） - 性能影响：O(log n)，但比手写少 2–3 行逻辑，编译器还能内联优化
- 示例：
auto it = std::lower_bound(v.begin(), v.end(), x); int pos = it - v.begin();
手写二分时 mid 计算必须用 l + (r - l) / 2
直接写 (l + r) / 2 在 l 和 r 都接近 INT_MAX 时会整数溢出，结果为负，后续下标访问直接 UB（未定义行为）。C++ 标准不保证溢出有符号整数的行为，GCC/Clang 可能静默 wrap-around，也可能触发 sanitizer 报错 runtime error: signed integer overflow。
- 永远用
mid = l + (r - l) / 2或mid = l + ((r - l) >> 1)（后者注意右移优先级） - 闭区间写法（
l ）适合需要精确控制退出条件的场景，比如找峰值或局部最小值 - 开区间写法（
l ）更贴近 STL 风格，循环结束时 <code>l == r即答案位置，不易多减一、少加一 - 别在 while 里反复调用
vec.size()，它不是 O(1)？不，它是 O(1)，但无谓调用增加可读干扰
自定义比较函数传给 std::lower_bound 的坑
如果你传了自定义 comp，它必须满足严格弱序（strict weak ordering）：不能有 comp(a,a)==true，且若 comp(a,b) 和 comp(b,c) 为真，则 comp(a,c) 也必须为真。否则 std::lower_bound 行为未定义，可能返回错误位置或崩溃。
立即学习“C++免费学习笔记（深入）”；
- 常见错误：用
!=或>=当比较函数；在 lambda 中捕获局部变量但生命周期已结束 - 使用场景：查找结构体中某个字段、按绝对值排序后的原索引定位、逆序数组上找上界（此时要传
std::greater()） - 示例：
std::lower_bound(v.begin(), v.end(), x, [](const auto& a, const auto& b) { return a.id - 注意：这个 lambda 的参数顺序是
(value, element)，和sort的(a,b)不同，别反着写
浮点数二分必须设 eps，但别用 == 判定终止
浮点数没有精确的「相等」概念，用 while (r - l > eps) 是安全的；用 while (l != r) 会陷入死循环，因为精度丢失导致差值永远大于 0 但无法收敛到目标。
- eps 选多少？一般
1e-7对 double 足够，但若值域很大（如1e9），相对误差更稳妥：while ((r - l) / std::max(1.0, std::abs(l)) > 1e-9) - 别在循环里反复计算
std::sqrt或std::sin，它们开销大，且可能引入额外误差 - 手写浮点二分时，mid 仍用
l + (r - l) / 2，不是(l + r) * 0.5（虽然后者数学等价，但前者更清晰、避免隐式转换歧义） - STL 不提供浮点数版
lower_bound，因为排序本身对浮点就不可靠，所以必须手写
真正麻烦的不是写对逻辑，而是确认你的数据是否真的满足「单调性」——比如函数在某段看似递增，实则因浮点舍入出现平台或微小震荡，这时候二分就失效了。
