最常用的二进制搜索变体由Hermann Bottenbruch于1962年首次发布,此后一直没有发生明显变化。下面,我将介绍几种具有改进性能的新颖变体。最显着的变体是单界二进制搜索,它对小于100万个32位整数的数组执行比标准二进制搜索快2到4倍的速度。 文件中提供了C语言中的源代码实现,该文件中还包含基准标记例程。包含性能结果的图形包含在此页面的底部。请记住,性能会因硬件和编译器优化而异。 我将在下面简要介绍每个变体和值得注意的优化。 递延平等检查 通过跳过对等的检测,直到二进制搜索完成(不允许提前终止),每个循环都包含1个键检查,1个整数检查和2个整数分配。这几乎是自1962年以来一直使用的标准算法。 指针优化 通过使用指针操作,您可以再提高10%的性能。我放弃了在C实现中的此类优化,以使内容尽可能保持可读性。 无符号整数优化 通过使用无符号而不是有符号整数,可以进一步提高性能。 稳