Advanced Search

Two Binary Search Functions in C

/ Published in: C
Save to your folder(s)
Two versions of binary search -- one recursive, one iterative -- for an array of strings.
Both assume that your array index fits within an integer.

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. /* iterative version */
  2. int search2(char *dict, char *name, int compChars) {
  3.     int low, high, mid, result;
  4.     low = 0;
  5.     high = SIZE_OF_DICTIONARY - 1;
  6.  
  7.     while (low <= high) {
  8.         mid = (low + high) / 2;
  9.         result = strncmp(dict[mid], name, compChars);
  10.         if (result > 0) {
  11.             high = mid - 1;
  12.         } else if (result < 0) {
  13.             low = mid + 1;
  14.         } else {
  15.             return EXIT_SUCCESS;
  16.         }   
  17.     }
  18.     return NOT_FOUND;
  19. }
  20.  
  21. /* recursive version -- takes more space and, for my money, is more confusing */
  22. int search(char *dict, char *name, int low, int high, int compChars) {
  23.     if (high < low) {
  24.         return NOT_FOUND; 
  25.     }
  26.     int mid = (low + high) / 2;
  27.     int result;
  28.     result = strncmp(dict[mid], name, compChars);
  29.     if (result > 0) {
  30.         return search(name, low, mid-1, compChars);
  31.     } else if (result < 0) {
  32.         return search(name, mid+1, high, compChars);
  33.     } else {
  34.         return EXIT_SUCCESS; 
  35.     }
  36.     return ERROR_SEARCH;
  37. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.