二分查找必须基于有序数组，否则结果不可靠；C++标准库函数如std::binary_search隐式依赖升序，无序数组将导致错误结果；动态数据应改用std::set/map；降序需手动实现或传std::greater()；循环实现比递归更安全高效；优先使用std::lower_bound而非手写；性能瓶颈常在于内存布局与缓存命中率而非算法本身。
二分查找必须要求数组有序，否则结果不可靠
这是最容易被忽略的前提。C++ 标准库的 std::binary_search、std::lower_bound 等函数都隐式依赖升序排列；若你传入无序数组，即使代码能跑通，返回值也毫无意义。实践中常见错误是：对原始数据只做了一次快排就以为“万事大吉”，却忽略了后续插入/修改后未重新排序，导致后续二分失效。
验证是否有序只需一次线性扫描：
bool is_sorted(const std::vector& arr) { for (size_t i = 1; i < arr.size(); ++i) if (arr[i] < arr[i-1]) return false; return true; }
- 调试阶段建议加该检查，上线后可移除（避免性能损耗）
- 若数据动态变化频繁，考虑改用
std::set或std::map，它们内部维持红黑树，天然支持对数时间查找 - 注意：降序数组也能用二分，但所有比较逻辑要翻转，且标准算法默认不支持，需手动实现或传自定义
std::greater()
循环实现比递归更安全，且避免栈溢出风险
递归写法看似简洁，但在 C++ 中容易因深度过大触发栈溢出——尤其当数组长度接近 INT_MAX 时，递归调用栈可能达数十万层。而循环版本空间复杂度稳定为 O(1)，且现代编译器对其优化更充分（如循环展开、条件预测）。
标准循环实现（查找目标值是否存在）：
立即学习“C++免费学习笔记（深入）”；
bool binary_search_iterative(const std::vector& arr, int target) { int left = 0, right = static_cast (arr.size()) - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止 left+right 溢出 if (arr[mid] == target) return true; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return false; }
-
mid = left + (right - left) / 2是必须写法，(left + right) / 2在left和right均为大正数时会整型溢出 -
right初始化为arr.size() - 1，不是arr.size()；否则越界访问 - 循环条件用
，不是，否则单元素数组会漏判
STL 的 lower_bound 比手写循环更值得优先使用
除非你在写算法题或教学演示，否则不建议自己重写二分逻辑。C++ 标准库的 std::lower_bound 经过高度优化，支持任意随机访问迭代器，且对缓存友好（连续内存访问模式）。它返回第一个不小于 target 的位置，配合 != arr.end() 和 == target 即可完成存在性判断。
auto it = std::lower_bound(arr.begin(), arr.end(), target); bool found = (it != arr.end() && *it == target);
- 若还需获取下标，用
std::distance(arr.begin(), it)，不要用it - arr.begin()（虽等价但可读性差） - 在
std::vector上，lower_bound实测比手写循环快 5%~10%，主要受益于底层 SIMD 指令和分支预测优化 - 注意：它要求迭代器满足
RandomAccessIterator，对std::list无效——此时应换容器，而非强行二分
查找效率受数据局部性影响，远大于算法常数差异
理论时间复杂度都是 O(log n)，但实际性能差距可能达 3 倍以上。关键变量不是循环还是递归，而是 CPU 缓存命中率。例如：一个 1GB 的 std::vector，即使二分只访问 ~30 个元素，但如果这些元素分散在不同内存页，每次访问都触发缺页中断，速度会暴跌。
- 确保数组内存连续（
std::vector天然满足，std::deque不满足） - 避免在二分过程中对数组做
push_back或erase，这会导致内存重分配和迭代器失效 - 若查找非常频繁且数据只读，考虑用
mmap将数组映射为只读内存，减少内核态拷贝
真正卡住性能的，往往不是二分本身，而是你没意识到：二分前的数据加载、排序、内存布局，已经决定了它的上限。
