- A+

Category：Languages

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.