有可能实现更快的二进制搜索吗？

最常用的二进制搜索变体最早由Hermann Bottenbruch于1962年发表，此后一直没有明显变化。下面我将描述几个性能更好的新型变种。最值得注意的变体是四进制二分搜索，它对32位整数的执行速度最高可提高25%。

C语言的源代码实现是可用的，许可使用GPL3(限制较少的许可可以协商)，并与基准测试例程捆绑在一起。此页底部包含一个包含性能结果的图表。

这些实现提供了稳定的搜索，这意味着如果一个数组包含多个副本，则返回最匹配的元素。下面我将简要描述每种变体。

通过跳过相等性的检测直到二进制搜索已经完成(这不允许提前终止)，每个循环存在1个密钥校验、1个整数校验和2个整数赋值。这几乎就是自1962年以来一直使用的标准算法。

这种二进制搜索变体具有与标准二进制搜索相同的键检查次数，只是计算稍微简单一些，从而使其性能提高1-2%，没有任何缺点。当密钥检查非常昂贵时，尾随二分搜索是一个很好的选择。

无限的二进制搜索比标准的二进制搜索更快，因为存在1个键检查、1个整数检查和(平均)1.5个整数赋值的循环。性能增益将因各种因素而异，但在比较32位整数时应大于5%。它执行更多的关键检查。

与无限二进制搜索相比，无限四分搜索具有更多的密钥检查，但运行速度更快。在我的大多数测试中，当比较32位整数时，它提供了15%到25%的性能提升。

由于边界问题，标准搜索中使用的MID-1优化不容易用于无限二进制搜索。入站二进制搜索解决了这个问题，并且随后比无限搜索具有更少的键检查。虽然它不如四进制二分查找快，但当密钥检查昂贵时，它可能会有一些实用程序。

当你有一个均匀的分布时，你就可以对索引的位置做出一个有根据的猜测。由于初始检查和纠错的开销，内插的二进制搜索不太可能在具有少于100个元素的阵列上优于其他二进制搜索。当分布不均匀时，性能会迅速下降，因此插值二分查找的实用性受到限制。

上图显示了在英特尔四核处理器上，对包含10、100、1,000、10000和100000个元素的数组进行千万次搜索的执行速度。Y轴以毫秒为单位列出执行时间。

在执行相同数量的密钥检查的同时，尾部二进制搜索(绿色)在所有情况下都比标准二进制搜索(红色)更有效。图表应该不言而喻。

0.000273秒内完成4271170次检查(STANDARD_BINARY_SEARCH)0.000266秒内完成4271170次检查(TAILED_BINARY_SEARCH)0.000283秒内完成4838276次检查(INBOUND_BINARY_SEARCH)0.000271秒内完成4986213次检查(BINDELSS_BINARY_SEARCH)0.000257秒内完成4986213次检查(BOUNLISE_QUTERNARY_SEARCH)0.000303秒内完成7410446次检查(内插搜索)。

0.000528秒内完成7714954次检查(STANDARD_BINARY_SEARCH)0.000499秒内完成7714954次检查(TAILED_BINARY_SEARCH)0.000473秒内完成7996715次检查(INBUND_BINARY_SEARCH)0.000462秒内完成9008149次检查(BINDELS_BINARY_SEARCH)0.000403秒内完成9008149次检查(BINDINED_QUARNARY_SEARCH)0.000345秒内完成9008149次检查(INTERPORTED_SEARCH)。

10978228次检查，耗时0.000750秒(STANDARD_BINARY_SEARCH)10978228次检查，耗时0.000727秒(TAILED_BINARY_SEARCH)10998884次检查，耗时0.000691秒(入站_BINARY_SEARCH)12567988次，耗时0.000677秒(BOUNLESS_BINARY_SEARCH)14971660次，耗时0.000557秒(BOUNLISH_QUARNARY_SEARCH)9843622次，耗时0.000457秒。

14362424次检查，耗时0.000960秒(STANDARD_BINARY_SEARCH)14362424次检查，耗时0.000940秒(TAILED_BINARY_SEARCH)14999472次检查，耗时0.000896秒(入站_BINARY_SEARCH)15879598次，耗时0.000886秒(BOUNLESS_BINARY_SEARCH)18629780次，耗时0.000764秒(BOUNLISH_QUARNARY_SEARCH)12435840次，耗时0.000556秒。

17688655个检查在0.001256秒内完成(STANDARD_BINARY_SEARCH)17688655个检查在0.001216秒内完成(TAILED_BINARY_SEARCH)17999976个检查在0.001166秒内完成(INBUND_BINARY_SEARCH)19040762个检查在0.001161秒内完成(BINDLESS_BINARY_SEARCH)22352836个检查在0.001009秒内完成(BOUNLESS_QUERNARY_SEARCH)0.000690秒内完成17999976个检查(INTERTAT

20951514次检查，耗时0.001773秒(STANDARD_BINARY_SEARCH)20951514次检查，耗时0.001721秒(TAILED_BINARY_SEARCH)20951514次检查，耗时0.001668秒(入站_BINARY_SEARCH)22528861次，耗时0.001667秒(BINDLESS_BINARY_SEARCH)26109365次，耗时0.001493秒(BOUNLISH_QUERNARY_SEARCH)1930,1928次，耗时0.001026秒