二分查找的实用效率
Practical Efficiency of binary search
在排序数组中搜索元素或插入点时，基本上有两种方法：直接搜索（逐个元素）或二分查找。从时间复杂度 O(n) vs O(log(n)) 我们知道二分搜索最终更有效，但这并不自动意味着二分搜索将 总是 比“正常搜索。
因此，我的问题是：二进制搜索实际上是否比低 n 的“正常”搜索效率低？如果是，我们能否估计二分查找效率更高的点？
谢谢！
是的，二进制搜索实际上可能比“正常”搜索小 n 的效率低。然而，这 很难估计 二分搜索在哪个点上会更有效（如果可能的话），因为这非常依赖于问题（例如数据类型、搜索谓词)、硬件（例如处理器、RAM）甚至执行搜索时使用的硬件的 动态状态 以及排序数组中的 实际数据 在现代系统上。
二分查找效率较低的第一个原因是矢量化。事实上，现代处理器可以支持处理相当大的向量的 SIMD 指令。因此，线性搜索可以在每个处理周期同时处理许多项目。现代处理器甚至经常可以在每个周期并行执行少量 SIMD 指令。虽然线性搜索通常可以被简单地矢量化，但二进制搜索却并非如此，因为它几乎本质上是顺序的。人们应该记住，矢量化并不总是可能的，也不总是由编译器自动完成，特别是在非平凡的 数据类型 （例如复合数据结构，基于指针的类型）或非琐碎的搜索谓词（例如带有条件或内存间接寻址的谓词）。
二分查找效率较低的第二个原因是分支可预测性。事实上，现代处理器试图提前预测分支以避免流水线停顿。如果此预测有效，则可以非常快速地进行分支，否则处理器可能会停顿几个周期（最多几十个）。如果分支总是为真或总是为假，则可以很容易地预测它。无法预测随机选择的分支会导致停顿。因为数组是排序的，所以线性搜索中的分支很容易预测（分支要么总是被采用，要么在找到元素之前永远不会被采用），而二分查找显然不是这种情况。因此，搜索速度取决于搜索的项目和排序数组中的数据。
同样的事情适用于缓存未命中和内存获取：因为RAM的延迟 与执行算术指令相比非常大，现代处理器包含专用的硬件预取单元，试图预测下一次内存获取并提前预取数据以避免缓存未命中。预取器可以很好地预测 linear/contiguous 内存访问，但对于 随机内存访问 非常不利。线性搜索的内存访问是微不足道的，而二进制搜索之一对于许多处理器来说似乎大多是随机的。在二进制搜索期间发生缓存未命中肯定会导致处理器停顿很多周期。如果已排序的数组已加载到缓存中，则对其进行二分查找会更快。
但这还不够：使用宽 SIMD 指令或缓存未命中会影响计算核心的频率，从而影响算法的速度。更不用说数据类型的大小也很重要，因为内存吞吐量有限，跨步内存访问比连续内存访问慢。人们还应该考虑到二进制搜索与线性搜索相比的额外复杂性（即通常需要执行更多指令）。我想我错过了上面列表中的一些重要点。
作为程序员，您可能需要定义一个阈值来选择使用哪种算法。如果您真的需要它，最好的解决方案是使用 benchmark 或 autotuning 方法自动查找。实际实验表明，对于给定的固定上下文（数据类型、缓存状态等），阈值在过去几十年发生了变化，有利于线性搜索（因此阈值通常会随着时间的推移而增加）。
我的个人建议 主流上 trivial/native 数据类型的 n 小于 256 / data_type_size_in_bytes 的值不要使用二进制搜索处理器。我认为当 n 大于 1000 时，或者当数据类型不平凡以及谓词昂贵时，使用二进制搜索是个好主意。
在排序数组中搜索元素或插入点时，基本上有两种方法：直接搜索（逐个元素）或二分查找。从时间复杂度 O(n) vs O(log(n)) 我们知道二分搜索最终更有效，但这并不自动意味着二分搜索将 总是 比“正常搜索。
因此，我的问题是：二进制搜索实际上是否比低 n 的“正常”搜索效率低？如果是，我们能否估计二分查找效率更高的点？
谢谢！
是的，二进制搜索实际上可能比“正常”搜索小 n 的效率低。然而，这 很难估计 二分搜索在哪个点上会更有效（如果可能的话），因为这非常依赖于问题（例如数据类型、搜索谓词)、硬件（例如处理器、RAM）甚至执行搜索时使用的硬件的 动态状态 以及排序数组中的 实际数据 在现代系统上。
二分查找效率较低的第一个原因是矢量化。事实上，现代处理器可以支持处理相当大的向量的 SIMD 指令。因此，线性搜索可以在每个处理周期同时处理许多项目。现代处理器甚至经常可以在每个周期并行执行少量 SIMD 指令。虽然线性搜索通常可以被简单地矢量化，但二进制搜索却并非如此，因为它几乎本质上是顺序的。人们应该记住，矢量化并不总是可能的，也不总是由编译器自动完成，特别是在非平凡的 数据类型 （例如复合数据结构，基于指针的类型）或非琐碎的搜索谓词（例如带有条件或内存间接寻址的谓词）。
二分查找效率较低的第二个原因是分支可预测性。事实上，现代处理器试图提前预测分支以避免流水线停顿。如果此预测有效，则可以非常快速地进行分支，否则处理器可能会停顿几个周期（最多几十个）。如果分支总是为真或总是为假，则可以很容易地预测它。无法预测随机选择的分支会导致停顿。因为数组是排序的，所以线性搜索中的分支很容易预测（分支要么总是被采用，要么在找到元素之前永远不会被采用），而二分查找显然不是这种情况。因此，搜索速度取决于搜索的项目和排序数组中的数据。
同样的事情适用于缓存未命中和内存获取：因为RAM的延迟 与执行算术指令相比非常大，现代处理器包含专用的硬件预取单元，试图预测下一次内存获取并提前预取数据以避免缓存未命中。预取器可以很好地预测 linear/contiguous 内存访问，但对于 随机内存访问 非常不利。线性搜索的内存访问是微不足道的，而二进制搜索之一对于许多处理器来说似乎大多是随机的。在二进制搜索期间发生缓存未命中肯定会导致处理器停顿很多周期。如果已排序的数组已加载到缓存中，则对其进行二分查找会更快。
但这还不够：使用宽 SIMD 指令或缓存未命中会影响计算核心的频率，从而影响算法的速度。更不用说数据类型的大小也很重要，因为内存吞吐量有限，跨步内存访问比连续内存访问慢。人们还应该考虑到二进制搜索与线性搜索相比的额外复杂性（即通常需要执行更多指令）。我想我错过了上面列表中的一些重要点。
作为程序员，您可能需要定义一个阈值来选择使用哪种算法。如果您真的需要它，最好的解决方案是使用 benchmark 或 autotuning 方法自动查找。实际实验表明，对于给定的固定上下文（数据类型、缓存状态等），阈值在过去几十年发生了变化，有利于线性搜索（因此阈值通常会随着时间的推移而增加）。
我的个人建议 主流上 trivial/native 数据类型的 n 小于 256 / data_type_size_in_bytes 的值不要使用二进制搜索处理器。我认为当 n 大于 1000 时，或者当数据类型不平凡以及谓词昂贵时，使用二进制搜索是个好主意。