Posted By

rtperson on 02/04/12


Tagged

search c binary


Versions (?)

Two Binary Search Functions in C


 / Published in: C
 

Two versions of binary search -- one recursive, one iterative -- for an array of strings. Both assume that your array index fits within an integer.

  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  

You need to login to post a comment.