The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 3.01 on page 58
Our 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.
Solution by Paul Griffiths
/* Solution by Paul Griffiths (mail@paulgriffiths.net) */ /* EX3_1.C ======= Suggested solution to Exercise 3-1 */ #include <stdio.h> #include <time.h> int binsearch(int x, int v[], int n); /* Original K&R function */ int binsearch2(int x, int v[], int n); /* Our new function */ #define MAX_ELEMENT 20000 /* Outputs approximation of processor time required for our two binary search functions. We search for the element -1, to time the functions' worst case performance (i.e. element not found in test data) */ int main(void) { int testdata[MAX_ELEMENT]; int index; /* Index of found element in test data */ int n = -1; /* Element to search for */ int i; clock_t time_taken; /* Initialize test data */ for ( i = 0; i < MAX_ELEMENT; ++i ) testdata[i] = i; /* Output approximation of time taken for 100,000 iterations of binsearch() */ for ( i = 0, time_taken = clock(); i < 100000; ++i ) { index = binsearch(n, testdata, MAX_ELEMENT); } time_taken = clock() - time_taken; if ( index < 0 ) printf("Element %d not found.\n", n); else printf("Element %d found at index %d.\n", n, index); printf("binsearch() took %lu clocks (%lu seconds)\n", (unsigned long) time_taken, (unsigned long) time_taken / CLOCKS_PER_SEC); /* Output approximation of time taken for 100,000 iterations of binsearch2() */ for ( i = 0, time_taken = clock(); i < 100000; ++i ) { index = binsearch2(n, testdata, MAX_ELEMENT); } time_taken = clock() - time_taken; if ( index < 0 ) printf("Element %d not found.\n", n); else printf("Element %d found at index %d.\n", n, index); printf("binsearch2() took %lu clocks (%lu seconds)\n", (unsigned long) time_taken, (unsigned long) time_taken / CLOCKS_PER_SEC); return 0; } /* Performs a binary search for element x in array v[], which has n elements */ int binsearch(int x, int v[], int n) { int low, mid, high; 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 return mid; } return -1; } /* Implementation of binsearch() using only one test inside the loop */ int binsearch2(int x, int v[], int n) { int low, high, mid; low = 0; high = n - 1; mid = (low+high) / 2; while ( low <= high && x != v[mid] ) { if ( x < v[mid] ) high = mid - 1; else low = mid + 1; mid = (low+high) / 2; } if ( x == v[mid] ) return mid; else return -1; }
Solution by Colin Barker
/* Solution by Colin Barker (colin.barker@wanadoo.fr) * using the driver from the solution by Paul Griffiths. */ /* EX3_1.C ======= Suggested solution to Exercise 3-1 */ #include <stdio.h> #include <time.h> int binsearch(int x, int v[], int n); /* Original K&R function */ int binsearch2(int x, int v[], int n); /* Our new function */ #define MAX_ELEMENT 20000 /* Outputs approximation of processor time required for our two binary search functions. We search for the element -1, to time the functions' worst case performance (i.e. element not found in test data) */ int main(void) { int testdata[MAX_ELEMENT]; int index; /* Index of found element in test data */ int n = -1; /* Element to search for */ int i; clock_t time_taken; /* Initialize test data */ for ( i = 0; i < MAX_ELEMENT; ++i ) testdata[i] = i; /* Output approximation of time taken for 100,000 iterations of binsearch() */ for ( i = 0, time_taken = clock(); i < 100000; ++i ) { index = binsearch(n, testdata, MAX_ELEMENT); } time_taken = clock() - time_taken; if ( index < 0 ) printf("Element %d not found.\n", n); else printf("Element %d found at index %d.\n", n, index); printf("binsearch() took %lu clocks (%lu seconds)\n", (unsigned long) time_taken, (unsigned long) time_taken / CLOCKS_PER_SEC); /* Output approximation of time taken for 100,000 iterations of binsearch2() */ for ( i = 0, time_taken = clock(); i < 100000; ++i ) { index = binsearch2(n, testdata, MAX_ELEMENT); } time_taken = clock() - time_taken; if ( index < 0 ) printf("Element %d not found.\n", n); else printf("Element %d found at index %d.\n", n, index); printf("binsearch2() took %lu clocks (%lu seconds)\n", (unsigned long) time_taken, (unsigned long) time_taken / CLOCKS_PER_SEC); return 0; } /* Performs a binary search for element x in array v[], which has n elements */ int binsearch(int x, int v[], int n) { int low, mid, high; 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 return mid; } return -1; } int binsearch2(int x, int v[], int n) { int low, high, mid; low = -1; high = n; while (low + 1 < high) { mid = (low + high) / 2; if (v[mid] < x) low = mid; else high = mid; } if (high == n || v[high] != x) return -1; else return high; }
Solution by Andrew Tesker
/* Andrew Tesker * * krx30102.c */ #include <stdio.h> /* find x in v[] */ int binsearch(int x, int v[], int n); /* The main is here for the purpose of a built in test */ int main(void) { int test[]={1,3,5,7,9,11,13}; int i; for(i=(sizeof(test)/sizeof(int))-1; i>=0; --i) printf("looking for %d. Index=%d\n",test[i],binsearch(test[i], test, sizeof(test)/sizeof(*test))); return 0; } /* n = size of array v */ 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; else low = mid+1; } return (x == v[low])?low : -1; }
Solution by Alejandro A. Buezo
/* Alejandro A. Buezo (aabuezo@yahoo.com.ar) * Date: 2017-17-09 */ /* * EX3_1.C * ======= * Just another suggested solution to Exercise 3-1 */ #include <stdio.h> int binsearch(int, int [], int); /* binary search by Kernighan and Ritchie */ int binsearch2(int, int [], int); /* Another binsearch */ #define MAX_ELEMENT 20000 int main(void) { int data_array[MAX_ELEMENT]; /* Ordered array of ints where to search for elements */ int values_to_check[] = {-1, 0, 1, 2, MAX_ELEMENT-1, MAX_ELEMENT, MAX_ELEMENT +1}; /* Elements to search for */ int size = sizeof(values_to_check) / sizeof(int); /* sizeof(values_to_check) */ int indexes[size]; /* Indexes of found elements in data_array */ int i; /* Initialize data */ for ( i = 0; i < MAX_ELEMENT; i++ ) data_array[i] = i; /* Testing binsearch */ for ( i = 0; i < size; i++ ) indexes[i] = binsearch(values_to_check[i], data_array, MAX_ELEMENT); /* Print binsearch results */ printf("binsearch:\n"); for( i = 0; i < size; i++) if ( indexes[i] < 0 ) printf("Element %d not found.\n", values_to_check[i]); else printf("Element %d found at index %d.\n", values_to_check[i], indexes[i]); /* Testing binsearch2 */ for ( i = 0; i < size; i++ ) indexes[i] = binsearch2(values_to_check[i], data_array, MAX_ELEMENT); /* Print binsearch2 results */ printf("binsearch2:\n"); for( i = 0; i < size; i++) if ( indexes[i] < 0 ) printf("Element %d not found.\n", values_to_check[i]); else printf("Element %d found at index %d.\n", values_to_check[i], indexes[i]); return 0; } /* binsearch: busca x en v[0] <= v[1] ... <= v[n] */ int binsearch(int x, int v[], int n) { int mid; int low = 0; int 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 return mid; } return -1; } /* binsearch2 */ int binsearch2(int x, int v[], int n) { int low, mid, high; low = 0; high = n-1; while( low <= high && x != v[mid = (low + high) / 2] ) { if( x < v[mid] ) high = mid - 1; else low = mid + 1; } return ( x == v[mid] ? mid : -1); } /* can be shorter int binsearch2(int x, int v[], int n) { int low, mid, high; low = 0; high = n-1; while( low <= high && x != v[mid = (low + high) / 2] ) ( x < v[mid] ) ? high = mid - 1 : low = mid + 1; return ( x == v[mid] ? mid : -1 ); } */ /* using n as high, but not so legible int binsearch2(int x, int v[], int n) { int low = 0, mid; n--; while( low <= n && x != v[mid = (low + n) / 2] ) ( x < v[mid] ) ? n = mid - 1 : low = mid + 1; return ( x == v[mid] ? mid : -1 ); } */
Solution by Luke Panayi
All these solutions putting condition checks at the top of the while loops are cheating!
#include <stdio.h> int binsearch(int x, int v[], int n) { int low, mid, high; low = 0; high = n-1; while (low < high) { mid = (low+high)/2; if (x <= v[mid]) high = mid; else low = mid + 1; } if (x == v[low]) return low; else return -1; } /* both functions are timed to 0.001 seconds (I guess it's easier to see the difference on CPU's from the 80's) however, in reality the new binsearch has a better worst case but a worse best cas as the old one would instantly return if input was best case, while the new one still has to iterate a few times, even if they're faster iterations. */ int main() { int var[] = {0,1,2,3,4,5,6,7,8,9}; printf("%d\n", binsearch(4,var,10)); return 0; }
Solution by Codybartfast (category 0)
With arrays containing 33M-134M items and then searching for each item I found a measurable difference in run-time with the modified version taking approx. 4% longer. The extra steps to terminate in the modified version being more expensive than the cost of the extra test in the original version.
| Size | Original | Modified | Diff |
| 2^25 | 4.042s | 4.188s | 3.6% |
| 2^26 | 8.365s | 8.551s | 2.2% |
| 2^27 | 16.854s | 17.818s | 5.7% |
(Each value the is average of 3 runs.
Timings made with linux 'time' command.)
#define SIZE 1 << 25 int binsearch(int x, int v[], int n); int values[SIZE]; int main(void) { int i, n = SIZE; for (i = 0; i < n; i++) values[i] = i; /* search for every item */ for (i = 0; i < n; i++) binsearch(i, values, n); return 0; } 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]) low = mid + 1; else high = mid; } return (x == v[low]) ? low : -1; }
