以下两种二分查找实现的性能差异

Question

我在《Competitive Programmer's Handbook》一书中看到了这两种二分查找的实现方式https://cses.fi/book/book.pdf。

方法一：


int a = 0, b = n-1; 

while (a <= b) { 
    int k = (a+b)/2; 
    if (array[k] == x) { 
        // x found at index k
    }
    if (array[k] > x) 
        b = k-1; 
    else
        a = k+1;
}

方法二：

int k = 0; 

for (int b = n/2; b >= 1; b /= 2){ 
    while (k+b < n && array[k+b] <= x) 
        k += b;
}
if (array[k] == x){ 
    // x found at index k
}

我想 方法 2 不完全是二进制搜索。我知道 method 1 和 method 2 都具有 O(log n) 复杂度。 方法 2 的代码也更简单，因此可能导致更少的错误。

我的问题是：

使用方法 2 时性能是否有任何改进？
方法2还有其他优势吗？

Answer 1

如此短的代码和如此少的差异，无法进行任何预测。时间性能将取决于编译器如何优化，但也取决于键在数组中的分布（特别是命中而不是未命中的概率）。

我不同意所有“反对”第二种方法的评论（甚至在完全正确的情况下声称有 buggy）。它基于一个可能使其变得更好的原则：循环体中只有一个测试。

比较是否相等（方法 1）给人一种错误的感觉，即算法会在找到密钥时提前终止并使搜索更快*。但这并非如此，因为对于一半的键来说，决策树的完整深度无论如何都是必要的，而且这不会因为有两个比较而不是一个比较而抵消。

*事实上，你平均只剩下一个次测试！

只有基准测试才能告诉您其中一种方法对于特定测试用例是否更快。我敢打赌运行次的分布重叠很多。（不考虑以一种能够代表其在真实环境中的行为的方式对如此快速的算法进行基准测试几乎是不可能的。）

最后评论：方法2是二元搜索，而实际上方法1是三元 !

以下两种二分查找实现的性能差异

Difference in performance between the following two implementations of binary search

algorithm

performance

binary-search

coding-efficiency

方法一：

方法二：