Why is linear search so much faster than binary search?

Consider the following code to find a peak in an array.

#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;
}

If I compile with -O3 and use the linear search solution (the peak function) it takes:

0.049 seconds

If I use the binary search solution which should be much faster (the peak_rec function), it takes:

5.27 seconds

I tried turning off optimization but this didn’t change the situation. I also tried both gcc and clang.

What is going on?

Answer

What is going on is that you’ve tested it in one case of a strictly monotonically increasing function. Your linear search routine has a shortcut that checks the final two entries, so it never even does a linear search. You should test random arrays to get a true sense of the distribution of runtimes.

Advertisement

Answer