线性搜索与二分搜索：理论与实际时间比差异过大的疑问

• 缓存友好性差异：线性搜索是连续遍历数组，完全契合CPU的缓存机制（L1/L2缓存能批量加载连续内存），几乎每次元素访问都能命中缓存，单步耗时极低；而二分搜索是跳跃式访问数组元素，缓存命中率极低，每次访问都可能需要从主存读取，主存延迟是缓存的几十倍，直接拉高了二分搜索的单步开销。
• 渐近复杂度的局限性：理论复杂度O(n)和O(log₂n)是n趋近于无穷大时的渐近趋势，它忽略了常数因子和低阶项。当n=1e5时，还没达到让常数因子可以忽略的量级，实际运行中这些被忽略的因素会极大缩小两者的耗时比值。
• 编译器优化与分支预测惩罚：线性搜索逻辑简单，编译器可以做循环展开、向量化等深度优化，把多步比较合并执行；而二分搜索依赖大量分支判断（比如判断中间值和目标值的大小），CPU的分支预测很容易失败，每次失败都会清空指令流水线，带来额外的性能损耗。
• 单步指令开销差异：线性搜索每轮仅需“读取元素-比较-索引自增”几个简单指令；二分搜索每轮需要计算中间索引（移位/除法操作）、分支判断、更新搜索边界，单步的指令数和执行成本远高于线性搜索。

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