17370845950

std::binary_search仅判断存在性而不返回位置，其本质区别于std::lower_bound；若容器未满足严格弱序（如自定义比较器漏写或顺序错误），行为未定义，可能导致误返回true。

std::binary_search 只能判断存在性，不能返回位置——这是它和 std::lower_bound 最本质的区别。

为什么 std::binary_search 找不到元素却返回 true？

常见错误是传入了非严格升序的 vector。它要求容器必须按「严格弱序」排序，比如重复元素没问题，但若用自定义比较器却漏写 而用了 ，行为未定义；或排序时用了 std::sort(v.begin(), v.end(), std::greater)，但查找时没传相同比较器，就会误判。

• 必须确保 vector 已用相同谓词排序（升序默认用 std::less）
• 若用 std::sort(v.begin(), v.end(), std::greater())，则查找必须写：

  std::binary_search(v.begin(), v.end(), 42, std::greater());

• 浮点数慎用：直接比较 double 值可能因精度导致结果不稳定

std::binary_search 和 lower_bound 性能一样快吗？

底层都是对数时间的二分查找，比较次数几乎相同，但 std::binary_search 略微轻量——它在找到匹配时立即返回 true，而 std::lower_bound 总是走到边界才停。不过这点差异在现代 CPU 上可忽略。

• 二者时间复杂度都是 O(log n)
• 如果后续还需知道位置（比如删/改/查后继），直接用 std::lower_bound 更高效，避免二次查找
• 没有迭代器开销差异：它们都不修改容器，也不分配内存

如何安全地用 binary_search 查找自定义类型？

关键在比较逻辑一致性。比如有个 struct Person { std::str

bool operator<(const Person& a, const Person& b) {
    return a.name < b.name; // 必须只依赖 name，且与 sort 用的完全一致
}

• 不能在比较器里混入 age，否则排序和查找的序不一致
• 查找时传字符串字面量要小心：std::binary_search(v.begin(), v.end(), "Alice") 会隐式构造 Person，需确保有对应构造函数或转换操作符
• 更稳妥写法是传完整对象：std::binary_search(v.begin(), v.end(), Person{"Alice", 0})

真正容易被忽略的是：当你需要“是否存在且位置在哪”时，别调两次 binary_search + lower_bound——那会多一次 O(log n) 开销。直接用 auto it = std::lower_bound(...); if (it != end && *it == value) { /* found at it */ } 更干净。