Why is linear search so much faster than binary search?

  • A+

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?


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.


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: