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