17370845950

应优先使用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 ）

面试/笔试里最容易栽在“找插入位置”和“找重复元素边界”

单纯“查是否存在”只是入门题；真实考点往往落在两个延伸场景：一是找目标值该插入到哪（保持有序），二是当数组含重复值时，找最左或最右出现位置。这两个需求，std::lower_bound 和 std::upper_bound 一行解决，手写则极易出错。

• 插入位置 = std::lower_bound(arr.begin(), arr.end(), target) - arr.begin()
• 最左下标 = std::lower_bound(...) 返回值；最右下标 = std::upper_bound(...) - 1（需先判断是否越界）
• 重复元素个数 = std::upper_bound(...) - std::lower_bound(...)，无需遍历
• 手写时若想求最右位置，不能简单把 改成 ，而要调整 left = mid + 1 和 right = mid 的分工，逻辑翻转容易绕晕

真正难的从来不是“怎么二分”，而是“在什么前提下用哪个接口、为什么这个接口在这里安全、换种容器会怎样”。细节堆叠起来，就是区分是否真懂的分水岭。