二分查找的实际效率：小规模n下是否低于普通顺序查找？

问题1：小数据规模下二分查找实际运行效率是否可能低于顺序查找？ #

结论是完全可能。
两种查找的单步操作开销差距很大：

• 顺序查找的单步仅包含下标自增、元素比对两个简单操作，连续的内存访问还能完美适配CPU的缓存预取机制，小数据量下缓存命中率接近100%，单步执行耗时极短
• 二分查找的单步需要完成中点计算、元素比对、区间边界更新三个操作，且每次访问的内存地址是跳跃的，更容易触发缓存失效，单步执行开销是顺序查找单步的数倍

当n极小时，比如n=8，顺序查找最坏情况下仅需8次比对，二分查找需要3次迭代，但3次二分迭代的总开销往往会超过8次顺序比对的总开销，最终表现就是顺序查找更快。

以下是两种查找的极简实现参考：

// 顺序查找
int linear_search(const int *arr, int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] >= target) return i;
    }
    return n;
}

// 二分查找
int binary_search(const int *arr, int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

问题2：是否可以估算二分查找效率高于顺序查找的临界数据规模？ #

临界规模确实存在，但没有通用的固定值，它主要受三类因素影响：

• 运行环境的硬件参数：CPU架构、缓存层级大小、指令集优化支持
• 数据本身的属性：数组元素的类型大小、自定义比对逻辑的复杂度
• 代码实现的优化程度：编译器是否开启循环展开、分支预测优化、二分实现是否有冗余判断

如果是常规x86桌面平台、数组存储基础数值类型（int/long等）、无特殊自定义比对逻辑的通用实现，实测下来临界规模通常在32~128区间。如果需要得到目标场景下的精确临界值，可以在对应运行环境做基准测试：遍历n从16到256的区间，分别统计两种查找的平均耗时，耗时曲线的交叉点对应的n值就是该场景的临界规模。 #

内容的提问来源于stack exchange，提问作者Raphael Tarita