C++二分查找怎么写 C++折半查找算法逻辑与实现【考点】_技术教程

应优先使用std::lower_bound和std::upper_bound，二者要求容器升序、时间复杂度O(log n)，可安全获取重复元素的左闭右开区间；手写需注意左闭右开循环条件、mid防溢出计算及边界更新逻辑；非随机访问容器（如list、set）须用对应成员函数以保效率。

std::lower_bound 和 std::upper_bound 是最稳妥的选择

标准库提供的 std::lower_bound 和 std::upper_bound 就是 C++ 里“二分查找”的事实标准，不是“可以选”，而是“应该优先用”。它们在头文件中，要求容器（或迭代器范围）已升序排列，时间复杂度稳定 O(log n)，且内部处理了边界、溢出、比较逻辑等所有易错点。

常见错误是手写循环时漏判 left == right 或混淆 和导致死循环或越界——而标准函数完全规避了这些。

std::lower_bound(first, last, val) 返回第一个 ≥ val 的位置（若不存在，返回 last）
std::upper_bound(first, last, val) 返回第一个 >
val 的位置
两者配合可直接得到值 val 在有序容器中的左闭右开区间：[lower_bound, upper_bound)
对 std::vector 使用时，确保已调用 std::sort；对 std::set 可直接用，因其天然有序

手写二分必须盯紧循环条件和边界更新

如果面试或题目明确要求“手写”，核心陷阱不在算法思想，而在三处细节：循环条件、mid 计算方式、左右指针更新逻辑。稍一松懈就进坑。

推荐统一用左闭右开区间 [left, right) 写法，避免 left 下的 right = mid - 1 易错组合：

int binary_search(const vector& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;  // 防止溢出，不用 (left + right) / 2
        if (arr[mid] < target) {
            left = mid + 1;  // 严格排除 mid，因 arr[mid] 已确定太小
        } else {
            right = mid;     // 不排除 mid，因 arr[mid] 可能就是 target
        }
    }
    return (left < arr.size() && arr[left] == target) ? left : -1;
}

用 left + (right - left) / 2 算 mid，防止 left + right 溢出（尤其在 int 范围大时）
循环条件始终是 left ，退出时 left == right，无需额外判断
else 分支用 right = mid（不是 mid - 1），因为 mid 位置仍可能是解
最后必须检查 left 是否越界，以及 arr[left] 是否真等于 target

STL 容器不同，二分接口不通用

不是所有“有序容器”都能无脑套用 std::lower_bound —— 关键看是否支持随机访问迭代器。这是常被忽略的兼容性问题。

std::vector、std::array、原生数组：支持随机访问，std::lower_bound 效率是 O(log n)
std::list、std::forward_list：只支持双向/单向迭代器，std::lower_bound 退化为 O(n)（它只能逐个走，无法跳转）
std::set、std::map：虽有序，但不提供 std::lower_bound 的高效版本（因底层是红黑树），应改用成员函数 set.lower_bound(val)，这才是 O(log n)
自定义类型需重载 operator，或传入比较函数（如 [](int a, int b) { return a ）