C++二分查找实现与binary_search用法解析

std::binary_search 返回 bool 因其仅用于判断元素是否存在，不提供位置信息；需获取下标或迭代器时应使用 std::lower_bound 或 std::upper_bound。

std::binary_search 为什么返回 bool 而不是下标

因为它的设计目标只有一个：**确认元素是否存在**。它不关心位置，所以不返回 int 或迭代器，只返回 true 或 false。如果你需要下标或迭代器，得用 std::lower_bound 或 std::upper_bound，而不是 std::binary_search。

常见错误是写成这样：

int pos = std::binary_search(v.begin(), v.end(), x); // ❌ 编译失败：返回类型是 bool

正确做法是先确保容器已排序，再单独查存在性：

• std::binary_search 要求范围必须是升序（默认）或按同一规则严格弱序
• 若用自定义比较函数，比如 std::greater()，则容器必须是降序排列，否则行为未定义
• 对 std::vector、std::array 等连续内存容器效率高；对 std::list 无法使用（不支持随机访问迭代器）

自己手写二分查找时，left <= right 还是 left < right

两种写法都对，但语义和边界处理逻辑不同，容易错在循环条件和更新方式的配合上。

推荐统一用 left < right + 左闭右开区间 [left, right)，理由是：避免 mid 计算溢出（可用 left + (right - left) / 2），且与 STL 迭代器习惯一致。

例如查找首个 ≥ x 的位置（即 lower_bound 行为）：

int lower_bound(const vector& a, int x) {
    int left = 0, right = a.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

• 若用 left <= right，需注意 right 初始化为 a.size() - 1，且循环内 right = mid - 1，否则可能死循环
• 手写时忘记检查越界（如 left == a.size()）会导致访问非法内存
• 整数除法向下取整，(left + right) / 2 在 left 和 right 很大时可能溢出，应改用 left + (right - left) / 2

binary_search 在 map/set 上能直接用吗

不能直接传迭代器范围调用 std::binary_search，因为 std::map 和 std::set 的 begin()/end() 返回的是双向迭代器，不是随机访问迭代器 —— 而 std::binary_search 要求 RandomAccessIterator。

但你不需要手动二分：这些容器内部就是平衡树，find()、count()、lower_bound() 都是 O(log n)，且更安全：

• my_map.find(x) != my_map.end() 比 std::binary_search 更自然、更高效（无需构造临时迭代器范围）
• std::binary_search(my_set.begin(), my_set.end(), x) 编译不过，报错类似：no match for ‘operator-’（缺少减法运算符）
• 若真要对 map 的 key 做二分，应提取 key 到 vector 再查，但通常没必要 —— 直接用 map.lower_bound(x)

用 binary_search 前忘了 sort 会怎样

结果不可预测：可能返回 true，也可能返回 false，即使元素真实存在。标准不保证任何行为，属于未定义（undefined behavior）。

典型误操作：

vector v = {5, 2, 8, 1};
bool found = binary_search(v.begin(), v.end(), 2); // ❌ 不排序就搜，结果随机

修复很简单，但要注意时机：

• 排序是一次性开销，如果后续多次查询，务必只排一次
• 若容器动态变化（插入/删除），每次查前都重新排序代价极高，此时应换用 std::set 或维护有序结构
• 用 std::sort 后再查，别漏掉头文件：#include 和 #include

最常被忽略的一点：自定义类型排序时，比较函数必须满足严格弱序（strict weak ordering），否则 sort 和 binary_search 都可能崩溃或返回错误结果。