std::lower_bound比手写二分更可靠，因其采用经充分测试的左闭右开区间实现，天然规避越界、漏判、死循环等off-by-one错误，并提供安全的存在性判断方式。
std::lower_bound 为什么比手写二分更可靠
手写 binary_search 容易越界、漏判边界、死循环，而 std::lower_bound 是标准库经过充分测试的实现，底层用的是「左闭右开」区间，天然规避多数 off-by-one 错误。
它返回第一个 ≥ 目标值的迭代器，配合 != vec.end() 和 *it == target 两步就能安全判断存在性。手写时若用「左闭右闭」，left 的循环条件和 <code>mid 更新方式稍有偏差就会卡住或越界。
- 必须传入随机访问迭代器（
vector、array可用，list不行） - 容器必须严格升序（不能含重复且无序，也不能是降序）
- 自定义类型需提供
运算符，或传入比较函数，如 <code>std::lower_bound(v.begin(), v.end(), x, [](int a, int b) { return a
手写二分时 mid 计算为什么不能写成 (left + right) / 2
当 left 和 right 都接近 INT_MAX 时，left + right 会整数溢出，结果为负数，后续计算彻底失控 —— 这不是理论风险，是真实踩过的坑，尤其在处理大数组索引或 long 类型下标时。
正确写法是 mid = left + (right - left) / 2，等价但不溢出。C++20 起也可用 std::midpoint(left, right)，它对有符号/无符号、指针都安全。
立即学习“C++免费学习笔记（深入）”；
- 如果用
size_t做下标（常见于vector.size()），right - left永远非负，但left + (right - left) / 2仍是首选，避免混淆 - 别依赖编译器优化：即使你确定数据小，也别省这个括号和减法，代码可移植性差一点，问题就出在生产环境的大内存机器上
查找失败时返回什么？不同函数行为差异很大
std::binary_search 只返回 bool，查不到就是 false，不告诉你位置；std::lower_bound 和 std::upper_bound 返回迭代器，失败时都等于 end() —— 但含义不同：lower_bound 指向第一个 ≥ 值的位置，upper_bound 指向第一个 > 值的位置。想查是否存在且取值，必须先判 != end()，再解引用比较。
- 误把
std::binary_search当作“返回下标”的函数，会导致编译错误（它没返回 int） - 用
std::lower_bound查找后直接*it而不检查是否== end()，会触发未定义行为（解引用尾后迭代器） - 若要找最后一个等于目标的元素，得组合用
lower_bound和upper_bound，而不是反复调用binary_search
vector 数据量多大时 std::lower_bound 才比线性扫描快
理论分界点是 log₂(n) ≈ n/100 —— 算下来 n ≈ 1000 就开始体现优势。实测中，n 256 后 std::lower_bound 稳定胜出。
- 如果数组是栈上小数组（如
int arr[16]），用std::lower_bound(std::begin(arr), std::end(arr), x)没问题，但别为了“看起来高级”强行套用 - 编译器对小范围循环可能自动向量化，而二分的跳转反而打断流水线，所以性能不是单纯看 O(log n)
- 真正影响性能的常是“是否已缓存”：若数组刚被遍历过，线性扫可能还在 L1 cache；若刚从磁盘读入且巨大，则二分的访存跳跃会放大 TLB miss
边界模糊的地方永远在“你实际的数据分布和访问模式”，不是教科书上的 n 值。
