binary_search

最常用的二分查找变体最初由 Hermann Bottenbruch 在 1962 年发表,此后并没有显著变化。下面我将介绍几种性能更优的新变体。最引人注目的变体是单边二分查找,在小于 100 万 32 位整数的数组上,其执行速度比标准二分查找快两到四倍。包含每种变体的 C 语言源代码实现可在 binary_search.c 文件中找到,该文件还包含一个基准测试程序。本页面底部附有性能结果图。请注意,性能会因硬件和编译器优化而有所差异。

下面我将简要描述每个变体和值得注意的优化，然后是一些性能图表。 延迟检测相等性 ------------------------------ 通过在二分查找完成之前跳过相等性检测（这不会允许提前终止），每个循环包含 1 次键检查、 1 次整数检查和 2 次整数赋值。 这基本上是自 1962 年以来一直使用的标准算法。 指针优化 ----------------------- 使用指针操作可以获得另外 10% 的性能提升。 在 C 实现中，我放弃了这种优化，以尽可能保持代码的可读性。

未签名整数优化----------------------------- 使用未签名整数可以进一步提高性能。 稳定性----------------- binary_search.c 中的所有实现都应是稳定的。 如果搜索包含元素 [1][4][7][7][7][9] 的数组，并且搜索数字 7，则应返回最右侧的索引。 如果要在稳定的排序算法中使用二分查找，就需要这样做。 二分查找是稳定的，不会明显降低性能。

在 binary_search.c 中的所有实现都应正确处理在搜索函数中以数组长度为 0 进行调用的情况。