std::binary_search返回bool因其仅用于判断存在性，不提供位置信息；需下标时应使用lower_bound配合相等检查，避免越界或误判插入点为找到点。
binary_search 为什么返回 bool 而不是下标
因为它的设计目标就只是「查存在性」，不是定位。你用 std::binary_search 只能知道某个值在已排序区间里有没有，不能知道它在哪——这和 std::lower_bound、std::upper_bound 的职责严格分开。
常见错误现象：binary_search 返回 true，但接着去取 arr[index]，结果 index 是错的，甚至越界；或者误以为它像 Python 的 bisect_left 那样返回位置。
- 使用场景：只做“是否存在”的快速判断（比如校验用户输入是否在白名单中）
- 参数差异：必须传入已严格升序（或按同一
Compare规则排序）的范围，否则行为未定义 - 性能影响：O(log n)，但比手写二分多一次函数调用开销，实际可忽略
- 示例：
std::vector
v = {1, 3, 5, 7, 9};
bool found = std::binary_search(v.begin(), v.end(), 5); // true
bool missing = std::binary_search(v.begin(), v.end(), 4); // false
想拿到下标？用 lower_bound + 检查相等
这是最常用也最安全的替代方案。因为 std::lower_bound 返回的是第一个 ≥ 目标值的迭代器，只要它没越界且所指元素等于目标，那就是你要的位置。
容易踩的坑：直接用 lower_bound 结果当“找到了”用，不检查 *it == value，导致把“插入点”当成“找到点”。
立即学习“C++免费学习笔记（深入）”；
- 使用场景：需要索引做后续操作（比如修改、删除、关联其他数组）
- 参数差异：同样要求区间已排序，且比较逻辑必须一致（比如自定义了
Compare，lower_bound和binary_search得传同一个） - 兼容性影响：C++98 起就有，无额外依赖
- 示例：
auto it = std::lower_bound(v.begin(), v.end(), 5);
if (it != v.end() && *it == 5) {
size_t idx = std::distance(v.begin(), it); // idx = 2
}
自己写二分时，边界条件怎么不写错
标准库不提供下标版 binary_search，就是怕你写错循环终止条件。手写最常崩在 left 还是 left ，以及 mid 怎么算、更新谁。
错误现象：死循环、漏掉端点、访问 v[n]（n 是 size）、对空容器崩溃。
- 推荐写法：统一用闭区间
[left, right]，初始化right = v.size() - 1，循环条件left ，更新后left = mid + 1或right = mid - 1 - mid 计算务必用
left + (right - left) / 2，避免left + right溢出（尤其用int存大索引时） - 空容器要单独判：
if (v.empty()) return -1; - 示例（返回下标，找不到返回 -1）：
int binary_search_idx(const std::vector
& v, int target) {
if (v.empty()) return -1;
int left = 0, right = v.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (v[mid] == target) return mid;
else if (v[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
自定义类型或降序排列怎么用 binary_search
所有基于比较的算法都依赖「严格弱序」，所以你必须显式传比较器，而且 binary_search 和排序用的必须是同一个。
典型翻车点：用 std::greater 排了降序，调 binary_search 却没传它，结果返回假阴性。
- 降序 vector：
std::vector
v = {9, 7, 5, 3, 1};
std::sort(v.begin(), v.end(), std::greater());
bool found = std::binary_search(v.begin(), v.end(), 5, std::greater()); - 自定义结构体：必须提供可调用对象（lambda、函数指针或重载
operator），且确保所有地方用同一套规则 - 注意：如果用了 lambda，得是 constexpr（C++17 起支持捕获空 lambda 作模板参数），否则只能用函数对象或
std::function（有运行时开销）
真正麻烦的从来不是“怎么写”，而是“怎么保证排序和查找用同一套逻辑”。哪怕只改一处比较符，整个二分就可能失效。
