std::vector必须有序才能正确使用std::lower_bound或std::binary_search，否则结果未定义；调用前需确保按升序（或对应自定义比较规则）排序，降序时须传入std::greater等匹配比较器。
std::vector必须有序才能用二分搜索
直接调用 std::binary_search 或 std::lower_bound 前，std::vector 必须已按升序（或自定义比较规则）排序。未排序时结果不可预测，不是“搜不到”，而是可能搜到任意位置——因为算法不检查顺序，只假设数据有序。
常见错误现象：std::binary_search(v.begin(), v.end(), x) 返回 false，但手动遍历发现 x 确实在里面；或者返回 true 却找不到对应迭代器。
- 排序只需一次：插入新元素后若破坏顺序，必须重新排序或用
std::lower_bound+insert维护有序性 - 升序是默认前提；若用降序，所有算法必须传入
std::greater<int>()</int>等对应比较器 -
std::sort时间复杂度 O(n log n)，后续每次查找才是 O(log n)
用std::lower_bound获取插入点或定位元素
std::lower_bound 比 std::binary_search 更实用：它返回第一个不小于目标值的迭代器，既能判断存在性，也能拿到位置，还能用于有序插入。
示例场景：查 5 是否存在，并获取其首次出现位置：
立即学习“C++免费学习笔记（深入）”；
auto it = std::lower_bound(v.begin(), v.end(), 5);
if (it != v.end() && *it == 5) {
size_t pos = std::distance(v.begin(), it); // 索引
}- 不要用
std::find替代——它退化为 O(n)，失去二分意义 - 返回迭代器而非索引，需用
std::distance转换；直接减法it - v.begin()也合法（vector迭代器支持随机访问） - 若目标不存在，
it指向第一个大于它的元素，或v.end()
自定义类型必须提供可比较的operator<或传入比较函数
对结构体或类使用二分搜索时，编译器无法自动知道“大小关系”。要么重载 operator<，要么每次调用都显式传入比较函数（lambda 或函数对象）。
错误写法：std::lower_bound(v.begin(), v.end(), obj) —— 若 MyClass 没定义 operator<，编译失败，报错类似 invalid operands to binary expression。
- 推荐 lambda 方式（尤其临时比较逻辑）：
[](const auto& a, const auto& b) { return a.id < b.id; } - 若比较逻辑固定，应在类内定义
bool operator<(const MyClass& rhs) const - 注意：比较函数签名必须与
std::lower_bound期望一致——前两个参数为待比元素，且语义是 “a < b”
性能关键：避免重复构造迭代器和边界检查
在循环中反复调用 std::lower_bound(v.begin(), v.end(), x) 是低效的：每次传入 v.begin()/v.end() 虽开销小，但现代编译器未必能完全优化掉冗余计算；更严重的是，如果 v 是局部变量且被频繁修改，边界可能失效。
- 把
begin/end提前存为变量，尤其在 tight loop 中：auto first = v.begin(), last = v.end(); - 确保
v在搜索期间不发生 realloc（如没调用push_back导致扩容），否则迭代器失效 - 对只读场景，考虑用
std::span<const T>（C++20）封装，明确传达不可变意图
二分搜索本身很快，但真正卡住性能的往往是排序、迭代器失效、或误以为无序容器也能用——这些地方一错，整个“快速”就没了。
