应使用std::lower_bound而非手写二分：它在已排序容器中找第一个不小于目标值的位置，高度优化、不易出错；用于左边界/首次出现查找，且比binary_search更实用，因可获插入位置。
用 std::lower_bound 而不是手写循环
标准库的 std::lower_bound 就是为这事儿写的：在已排序容器中找第一个不小于目标值的位置。它经过高度优化，支持随机访问迭代器（如 vector、数组），内部用的是混合策略（比如分段展开 + 分支预测友好写法），比多数人手写的二分快且不易出错。
常见错误现象：while (left 边界写反、<code>mid 溢出（(left + right) / 2 在大索引时整数溢出）、漏掉 == 判断分支导致逻辑错位。
- 必须确保输入容器/数组已升序排列，否则行为未定义
- 返回的是迭代器，要取下标得减去
begin()：std::lower_bound(v.begin(), v.end(), x) - v.begin() - 如果只查存在性，别用
std::binary_search—— 它不返回位置，还得再调一次lower_bound才能定位，白费一次遍历
std::lower_bound 的自定义比较函数怎么写才安全
当你查的是结构体、或需要按字段比较时，传比较函数最常用。但容易踩坑的是：比较函数必须满足「严格弱序」，否则 std::lower_bound 可能无限循环或返回错误位置。
使用场景：查 vector<Person> 中年龄 ≥ 30 的第一个人；或按字符串长度二分。
立即学习“C++免费学习笔记（深入）”；
- 比较函数签名应为
bool( const T&, const U& )或bool( const U&, const T& )，两边类型可不同（支持查找int在vector<long>中） - 避免在比较函数里做耗时操作（如字符串
substr、文件读取），它会被多次调用 - 错误示例：
[&](const Person& a, int age) { return a.age <= age; }—— 这违反了严格弱序（<=不是严格小于），应改用<
数组原生指针也能用 std::lower_bound，但要注意迭代器类型
很多人以为 std::lower_bound 只能用于 STL 容器，其实它接受任意随机访问迭代器，包括原生指针。这对面试写“无容器依赖”的代码很实用。
性能影响：指针版本零额外开销，和手写汇编级二分几乎等效；兼容性上，C++11 起完全支持。
- 正确写法：
int* p = std::lower_bound(arr, arr + n, x);，返回的是int*，不是下标 - 别写成
std::lower_bound(&arr[0], &arr[n], x)——&arr[n]是越界指针（哪怕没解引用），UB 风险 - 如果数组是
const int arr[N]，要用const int*类型传入，否则编译失败
为什么不用 std::upper_bound 替代 lower_bound？
两者语义不同：lower_bound 找第一个 ≥ x 的位置，upper_bound 找第一个 > x 的位置。面试题常要求“左边界”“第一次出现”，这时必须用 lower_bound；若混用，结果可能偏移一位，尤其当目标值重复出现时。
容易被忽略的地方：即使你只想判断存在性，也建议统一用 lower_bound + 比较值，而不是 binary_search —— 因为后者无法告诉你插入点在哪，而实际工程中，查完紧接着要插入/修改的情况远多于单纯判断。
一个典型陷阱：对 [1,2,2,2,3] 查 2，lower_bound 返回索引 1，upper_bound 返回索引 4；差值就是频次，但如果你记混了谁是谁，整个区间统计就全错。
