为什么线性搜索比二分搜索快得多？

Question

请考虑以下代码以在数组中查找峰值.

#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.

到底是怎么回事？

Answer 1

结果是你在一个严格单调递增函数的情况下测试了它.您的线性搜索例程有一个快捷方式,可以检查最后两个条目,因此它甚至不会进行线性搜索.您应该测试随机数组以真正了解运行时的分布.