应优先使用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 易错组合：
立即学习“C++免费学习笔记（深入）”；
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的分工，逻辑翻转容易绕晕
真正难的从来不是“怎么二分”，而是“在什么前提下用哪个接口、为什么这个接口在这里安全、换种容器会怎样”。细节堆叠起来，就是区分是否真懂的分水岭。
