std::binary_search 必须用于已排序容器，因其仅执行二分查找而不验证有序性，未排序时行为未定义；适用随机访问迭代器容器如 vector、deque、原生数组，list 等不支持。
std::binary_search 为什么必须用排序容器
因为 std::binary_search 内部只做对半查找，不验证数据是否有序。如果容器未排序，结果完全不可靠——可能返回 false 即使元素存在，也可能返回 true 却找不到对应迭代器（它不返回位置）。标准明确要求“行为未定义”。
常见错误现象：std::binary_search(v.begin(), v.end(), x) 在 std::vector 上返回 false，但手动遍历发现 x 确实在里面——大概率是忘了调用 std::sort 或插入后没维护顺序。
- 适用容器：必须支持随机访问迭代器，如
std::vector、std::deque、原生数组；std::list和std::forward_list不可用 - 排序依据：默认用
比较，若自定义类型需提供operator 或传入比较函数对象 - 注意：
std::set/std::map虽然有序，但迭代器不是随机访问类型，不能直接套用该函数（得用find()）
和 std::lower_bound + 比较判等相比，哪个更快
理论上几乎一样快——std::binary_search 底层通常就是调用 std::lower_bound 再判断值是否相等。但关键差异在语义和用途：
- 只关心“是否存在”：用
std::binary_search更清晰，代码意图明确 - 需要获取位置或后续操作（如插入点、范围统计）：必须用
std::lower_bound或std::upper_bound，再自行比较 - 性能上无实质差别，但编译器对
std::binary_search可能做更激进的优化（比如提前终止），实际差异可忽略
示例：检查 val 是否在已排序的 vec 中
bool found = std::binary_search(vec.begin(), vec.end(), val);
等价于：
auto it = std::lower_bound(vec.begin(), vec.end(), val); bool found = (it != vec.end() && *it == val);
自定义比较函数时最容易漏掉的约束
传给 std::binary_search 的比较函数必须满足“严格弱序”（strict weak ordering），否则行为未定义。最常踩的坑是写成 、或在浮点数比较中直接用 ==。
- 错误写法：
[](double a, double b) { return a → 违反“非自反性”，comp(x,x)返回true - 浮点安全写法：
[](double a, double b) { return a （慎用，推荐用std::abs(a-b) 配合lower_bound手动查） - 结构体比较：确保所有字段参与比较，且逻辑一致，例如
if (a.id != b.id) return a.id ，再比name，不能漏掉分支
在 vector 中反复查找时，别让 sort 成为性能瓶颈
如果容器内容不变，只做多次查找，std::sort 只需调用一次。但很多人在循环里重复调用 std::sort，导致 O(n log n × m) 时间爆炸。
- 正确做法：初始化后一次性排序，后续所有
std::binary_search都是 O(log n) - 若容器动态增删：考虑改用
std::set（O(log n) 插入+查找），或用std::vector+ 手动std::lower_bound+std::insert维护有序（插入 O(n)，适合读多写少） - 小数据量（n std::find 可能比二分更快——cache 友好，分支预测稳定，别盲目迷信 O(log n)
真正容易被忽略的是：排序和查找的比较逻辑必须完全一致。比如排序用 std::less，查找却传了自定义 lambda，结果一定错。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
