c++ - 为什么线性搜索比二进制搜索快得多？

Question

考虑以下代码 find a peak在数组中。

#include<iostream>
#include<chrono>
#include<unistd.h>


using namespace std;

//Linear search solution
int peak(int *A, int len)
{
    if(A[0] >= A[1])
        return 0;
    if(A[len-1] >= A[len-2])
        return len-1;

    for(int i=1; i < len-1; i=i+1) {
        if(A[i] >= A[i-1] && A[i] >= A[i+1])
            return i;
    }
    return -1;
}

int mean(int l, int r) {
    return l-1 + (r-l)/2;
}

//Recursive binary search solution
int peak_rec(int *A, int l, int r) 
{
    // cout << "Called with: " << l << ", " << r << endl;
    if(r == l)
        return l;
    if(r == l+ 1)
        return (A[l] >= A[l+1])?l:l+1;

    int m = mean(l, r);

    if(A[m] >= A[m-1] && A[m] >= A[m+1])
        return m;

    if(A[m-1] >= A[m])
        return peak_rec(A, l, m-1);
    else
        return peak_rec(A, m+1, r);
}


int main(int argc, char * argv[]) {
    int size = 100000000;
    int *A = new int[size];
    for(int l=0; l < size; l++)
        A[l] = l;

    chrono::steady_clock::time_point start = chrono::steady_clock::now();   
    int p = -1;
    for(int k=0; k <= size; k ++)
//      p = peak(A, size);
        p = peak_rec(A, 0, size-1);

    chrono::steady_clock::time_point end = chrono::steady_clock::now(); 

    chrono::duration<double> time_span = chrono::duration_cast<chrono::duration<double>>(end - start);

    cout << "Peak finding: " << p << ", time in secs: " << time_span.count() << endl;

    delete[] A;
    return 0;
}

如果我使用 -O3 编译并使用线性搜索解决方案(peak 函数)，它需要:

0.049 seconds

如果我使用应该更快的二进制搜索解决方案(peak_rec 函数)，它需要:

5.27 seconds

我尝试关闭优化，但这并没有改变这种情况。我还尝试了 gcc 和 clang。

What is going on?

Answer 1

发生的事情是您已经在一个严格单调递增函数的情况下对其进行了测试。您的线性搜索例程有一个检查最后两个条目的快捷方式，因此它甚至从不进行线性搜索。您应该测试随机数组以真正了解运行时的分布。