#include #include //malloc, srand, rand, NULL #include //time and clock_t #define N 100000 /** * The purpose of this code is to examine the performance differences between 2 methods of binary search. * Exercise from The C Programming Language, 2nd Edition; Brian W. Kernighan and Dennis M. Ritchie * Our (the book's) binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time. * This is my solution to the problem. */ int binSearch(int, int[], int); int bSearch(int, int[], int); int main() { srand(time(NULL)); int *arr = malloc(N*sizeof(int)); if(!arr) { perror("System allocation fail!"); return -1; } int i, x; x = rand()%N; for(i=0; i tRunBin ? "binSearch" : tRunB < tRunBin ? "bSearch": "Neither"); //printf("binSearch runtime: %f\nbSearch runtime: %f", tRunBin, tRunB); free(arr); return 0; } /* * Code found in The C Programming Language, 2nd Edition; Brian W. Kernighan and Dennis M. Ritchie * binSearch: find x in v[0] <= v[1] <= … <= v[n-1] * This is typically how a binary search is written. * @param x – value to find * @param v – vector of numbers to check * @param n – size of vector */ int binSearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n-1; while(low <= high) { mid = (low+high)/2; if(x < v[mid]) high = mid-1; else if(x > v[mid]) low = mid+1; else /* found match */ return mid; }//end while return -1; /* no match */ } /* * My implementation of same code but only one test inside the loop * bSearch: find x in v[0] <= v[1] <= … <= v[n-1] * @param x – value to find * @param v – vector of numbers to check * @param n – size of vector */ int bSearch(int x, int v[], int n) { int low = 0, high = n, mid; while (low < high) { mid = low + ((high - low) / 2); if (v[mid] < x) low = mid + 1; else /*can't be high = mid-1: here v[mid] >= x, so high can't be < mid if v[mid] == x*/ high = mid; } // high == low, using high or low depends on taste if ((low < n) && (v[low] == x)) return low; // match else return -1; // no match }

Binary Search Performance Tests