17370845950

二分查找必须基于有序数组，否则结果不可靠；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)，且现代编译器对其优化更充分（如循环展开、条件预测）。

标准循环实现（查找目标值是否存在）：

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 将数组映射为只读内存，减少内核态拷贝

真正卡住性能的，往往不是二分本身，而是你没意识到：二分前的数据加载、排序、内存布局，已经决定了它的上限。