bsearch.c 1001 B

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
  1. /* bsearch(3)
  2. *
  3. * Author: Terrence Holm Aug. 1988
  4. *
  5. *
  6. * Performs a binary search for a given <key> within a sorted
  7. * table. The table contains <count> entries of size <width>
  8. * and starts at <base>.
  9. *
  10. * Entries are compared using keycmp( key, entry ), each argument
  11. * is a (char *), the function returns an int < 0, = 0 or > 0
  12. * according to the order of the two arguments.
  13. *
  14. * Bsearch(3) returns a pointer to the matching entry, if found,
  15. * otherwise NULL is returned.
  16. */
  17. #define NULL (char *) 0
  18. char *bsearch( key, base, count, width, keycmp )
  19. char *key;
  20. char *base;
  21. unsigned int count;
  22. unsigned int width;
  23. int (*keycmp)();
  24. {
  25. char *mid_point;
  26. int cmp;
  27. while ( count > 0 )
  28. {
  29. mid_point = base + width * (count >> 1);
  30. cmp = (*keycmp)( key, mid_point );
  31. if ( cmp == 0 )
  32. return( mid_point );
  33. if ( cmp < 0 )
  34. count >>= 1;
  35. else
  36. {
  37. base = mid_point + width;
  38. count = (count - 1) >> 1;
  39. }
  40. }
  41. return( NULL );
  42. }