教科书里那句「有序数组查值二分查找 O(log n) 永远比 O(n) 的线性扫描快」我在本机真跑了一遍结果它只说对了一半当数组只有 8 个元素时二分查找平均每条查询 6.65ns而线性扫描只要 4.60ns——二分反而慢了约 1.5 倍。O(log n) 是 asymptotics不是热水壶凉的数组不会因为它「渐近更优」就自动变快。这篇复盘的不是一个冷知识而是一次把「复杂度」和「真实墙钟时间」对齐的实测。背景为什么教科书没告诉你答案复杂度分析算的是「比较次数」线性最坏 n 次二分最坏 log₂n 次。这个账从 1946 年 Newman–Stroud 把二分写成算法起就没错。问题在于比较次数 ≠ CPU 真的花的纳秒数。现代处理器有三笔账教科书默认不收分支预测器、缓存预取、SIMD 向量化。线性扫描顺着内存地址一路读下去预取器能提前把下一行搬进 L1分支几乎「总是命中 / 总是不命中」极易预测二分每次跳到中点内存访问近乎随机、分支走向随数据翻转预取失效、预测器失误流水线被清空一次就要几十个周期。小数组上这几笔「固定开销」反而压过了比较次数省下的那一点点。更反直觉的是 2026 年 Daniel Lemire 的实测在「线性 vs 二分」之外用四路探针 SIMD 的 Quad 算法在冷缓存下能比标准二分还快两倍以上——因为标准算法诞生时CPU 还没有今天这么多的数据级与内存级并行。也就是说「比二分更快」这条路本身就存在只是它信赖硬件而非纯逻辑。解剖教科书 O(log n) 漏算的两笔账把二分和线性拆开差异集中在两点第一笔是内存访问模式。线性扫描访问a[0], a[1], a[2]…是连续的缓存行 64 字节一次装 16 个 32 位整数命中率高二分访问a[mid]mid每次折半跳来跳去每次都可能跨缓存行甚至跨页冷缓存下一次 miss 就要上百纳秒。第二笔是分支可预测性。线性扫描在命中前分支走向一致一路! target预测器几乎不失误二分每次if (a[mid] target)的走向随数据随机翻转是经典的「不可预测分支」。图1横轴为数组规模 n8→4096纵轴为单次查询平均墙钟时间纳秒对数刻度。蓝线为线性扫描橙线为二分查找。两线在 n8 到 n16 之间交叉——在此之前线性更便宜在此之后二分碾压。实证我在本机跑出的真实基准我没有引用别人的图表而是用 Node 22.22.2 在本机win32 x64跑了 10 个规模、每组 1024 条混合命中/未命中查询、重复 2000 轮。数组为有序Uint32Array查询分组缓存warm cache更接近「同一张小表反复查」的真实工况。三个实现逐元素线性、lo (hi - lo) 1的标准二分、以及受 Lemire 启发的四路探针 二分混合。function binarySearch(a, target) { let lo 0, hi a.length - 1; while (lo hi) { const mid lo ((hi - lo) 1); // 防溢出写法不用 (lohi)/2 const m a[mid]; if (m target) return mid; if (m target) lo mid 1; else hi mid - 1; } return -1; }实测关键数字单次查询平均 nsn线性扫描二分查找四路探针线/二 比值84.606.654.810.69线性快 1.5×169.497.145.501.33二分反超6426.716.705.923.9825694.108.457.0911.11024332.288.998.8937.040961237.0311.2110.05110.3结论很干净交叉点稳稳落在n8 与 n16 之间。n≤8 时线性比二分便宜约 1.5 倍n4096 时线性已被甩开 110 倍。四路探针在 n≥16 后始终贴着或略优于纯二分大 n 下约快 10%在小 n 上退化回和线性同档4.81 vs 4.60说明「探针开销」对小表同样不划算。图2左侧线性扫描是一条顺序的内存流预取器与分支预测器各司其职右侧二分每次跳到随机中点预取失效、分支翻转引来缓存 miss 与流水线清空。小数组上这些「固定税」盖过了比较次数的优势。为什么小数组上二分反而输把数字翻成直觉线性扫描在 n8 时平均走 4 步、n16 时约 8 步全是「顺序读 一个好预测分支」二分在 n8 时也要算mid、做除法/位移、判断分支、跳地址——逻辑本身更重。当数组整个能装进一两条缓存行时「少比较几次」让出来的时间远不够补偿二分那一连串跳转与分支失误。这其实不是我拍脑袋JDK 的Arrays.binarySearch在长度小于 21 时直接退化为 for 循环线性遍历Knuth 早在 MIX 模型上就给出过「二分仅在 n44 时才胜过带哨兵的线性」的结论。工程界的统治者们早就把「小表别二分」写进了标准库。我本机的交叉点8~16比 Knuth 的 44 更激进正是因为今天的预取器与分支预测比 MIX 强得多——也就是说随硬件演进这个交叉点还在持续左移。还能更快四路探针 二分的混合打法既然「标准二分」不是终点一个务实的混合策略是三层阈值小表线性、中表二分、并让四路探针在大表上接管。四路探针的思路是先读 4 个均匀分布的哨兵值a[q-1], a[2q-1], a[3q-1]用 3 次比较把搜索区间一次性砍到 1/4再在四分之一段里跑普通二分。它省下的不是比较次数而是「内存级并行」——一次把四个哨兵都取进寄存器比逐次折半更贴合现代 CPU 的取指能力。function quadSearch(a, target) { const n a.length; if (n 4) return binarySearch(a, target); const q n 2; const k1 a[q - 1], k2 a[2 * q - 1], k3 a[3 * q - 1]; let lo, hi; if (target k1) { lo 0; hi q - 1; } else if (target k2) { lo q; hi 2 * q - 1; } else if (target k3) { lo 2 * q; hi 3 * q - 1; } else { lo 3 * q; hi n - 1; } // 以下同标准二分…… return binarySearchRange(a, target, lo, hi); }诚实地说我的 warm-cache 基准里四路探针只比纯二分快约 10%远没到 Lemire 冷缓存下「两倍」的量级——因为本机测试用的是顺序友好的 32 位定长数组预取器本来就不亏。真正的 Quad 红利出现在「冷缓存 内存级并行」的服务器端工况。所以这条打法的价值是「方向上正确幅度看硬件」不该被当成银弹。图3以 n 为横轴的选型卡。n≤8 用线性最省固定税n16~数百用标准二分n 很大且数据集大/冷缓存时四路探针 二分混合更稳。阈值随硬件左移应以本机基准为准。局限这些数字不能怎么外推三句话把边界讲清楚。其一我的基准是 warm cache、定长Uint32Array、命中/未命中各半换成「冷缓存」或「每条查询查不同数组」线性的劣势会放大、四路探针的优势也会放大结论的幅度会变但「小 n 线性更便宜、大 n 二分碾压」的定性不变。其二对象数组 / 指针型比较如按 key 取结构体会让线性失去顺序友好的优势交叉点右移标准库阈值如 JDK 的 21就是为这类情况留的余量。其三单次查询的绝对 ns 数随 CPU、内存、Node 版本漂移可复现的是「交叉点的位置」而非某个精确数值——所以任何选型都应以你自己的console.time为准。结论与下一步一句话方法论O(log n) 是渐近结论不是墙钟保证小数组先用线性大数组再上二分必要时用四路探针吃硬件并行红利——阈值永远靠本机基准定不靠教科书背。别再在 8 个元素的配置表里写二分了它此刻比 for 循环慢一半。开源地址结论段指向同一组织即可3 个矩阵门户https://github.com/wangzifan396-wzf/WB单文件工具聚合器https://github.com/wangzifan396-wzf/nano-workbenchGitHub 组织主页https://github.com/wangzifan396-wzf