二分查找必须在有序数组上进行，无序时结果不可预测；C++标准库相关算法均要求严格弱序，使用前需用std::sort排序，注意保留原索引；std::binary_search仅判断存在性最安全，但不返回位置；手写需防溢出和死循环，空容器须特判；lower_bound更实用，支持插入定位与重复元素处理。
二分查找必须要求数组有序
无序数组上调用二分查找，结果不可预测，std::lower_bound 或手写 binary_search 都会返回错误位置或假阴性。C++ 标准库所有二分算法（binary_search、lower_bound、upper_bound、equal_range）均假设迭代器区间已按严格弱序排序（默认升序）。若数据来自用户输入或动态生成，务必先调用 std::sort —— 但注意：排序会改变原顺序，如需保留原始索引，得用索引数组或 std::vector<:pair size_t>></:pair> 配合自定义比较。
用 std::binary_search 判断存在性最安全
它只返回 bool，不暴露迭代器细节，避免越界或误用指针。适合“查有没有”这种简单场景：
std::vector<int> arr = {1, 3, 5, 7, 9};
bool found = std::binary_search(arr.begin(), arr.end(), 5); // true
found = std::binary_search(arr.begin(), arr.end(), 4); // false注意三点：
-
std::binary_search不接受自定义比较的重载版本用于判断“相等”，它内部用!comp(value, *it) && !comp(*it, value)检查，所以传入的比较函数必须满足严格弱序（比如std::less），不能是或其他非严格逻辑 - 搜索值类型必须能与容器元素隐式比较；若为自定义类型，需重载
operator 或传入对应 <code>Compare对象 - 它不保证返回第一个/最后一个匹配项——要定位位置，必须用
lower_bound
手写循环版二分要防整数溢出和死循环
常见错误是写 mid = (left + right) / 2 导致 left + right 溢出（尤其 int 存大索引时）。正确写法是 mid = left + (right - left) / 2。另外，边界更新必须严格排除已判定不可能的位置，否则可能卡在两元素区间无限循环：
立即学习“C++免费学习笔记（深入）”；
int binary_search(const std::vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1; // 必须 +1，否则 left==mid 时卡住
else right = mid - 1; // 必须 -1，否则 right==mid 时卡住
}
return -1;
}这个版本返回下标，找不到返回 -1。但要注意：当 arr 为空时，arr.size() - 1 是极大正数（因为 size() 返回 size_t），直接导致未定义行为。稳妥做法是开头加 if (arr.empty()) return -1;。
用 std::lower_bound 获取插入位置更实用
实际开发中，“找某个值”往往是为了后续插入或批量处理。此时 std::lower_bound 返回第一个不小于目标值的迭代器，天然支持重复元素的左边界定位，且返回类型是迭代器，可直接用于 insert 或计算距离：
auto it = std::lower_bound(arr.begin(), arr.end(), 6); int pos = it - arr.begin(); // 得到插入位置下标 // 若想插入并保持有序：arr.insert(it, 6);
关键点：
- 它不要求元素唯一，重复时总指向第一个匹配项（或首个更大项）
- 即使目标不存在，返回的迭代器也合法（可能是
end()），可安全做减法算位置 - 若容器是
std::set或std::map，应改用成员函数lower_bound，性能更好（红黑树 O(log n)，而非泛型算法的随机访问假设）
边界情况最容易被忽略的是空容器和全小于/全大于目标值的情形——lower_bound 在这些情况下分别返回 begin() 和 end()，必须检查 it != arr.end() && *it == target 才能确认找到，不能只看是否等于 end()。
