Revision: 55374
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at February 4, 2012 02:45 by rtperson
Initial Code
/* iterative version */ int search2(char *dict, char *name, int compChars) { int low, high, mid, result; low = 0; high = SIZE_OF_DICTIONARY - 1; while (low <= high) { mid = (low + high) / 2; result = strncmp(dict[mid], name, compChars); if (result > 0) { high = mid - 1; } else if (result < 0) { low = mid + 1; } else { return EXIT_SUCCESS; } } return NOT_FOUND; } /* recursive version -- takes more space and, for my money, is more confusing */ int search(char *dict, char *name, int low, int high, int compChars) { if (high < low) { return NOT_FOUND; } int mid = (low + high) / 2; int result; result = strncmp(dict[mid], name, compChars); if (result > 0) { return search(name, low, mid-1, compChars); } else if (result < 0) { return search(name, mid+1, high, compChars); } else { return EXIT_SUCCESS; } return ERROR_SEARCH; }
Initial URL
Initial Description
Two versions of binary search -- one recursive, one iterative -- for an array of strings. Both assume that your array index fits within an integer.
Initial Title
Two Binary Search Functions in C
Initial Tags
search, c
Initial Language
C