home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / vc98 / crt / src / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-06-17  |  2.4 KB  |  78 lines
  1. /***
  2. *bsearch.c - do a binary search
  3. *
  4. *       Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *       defines bsearch() - do a binary search an an array
  8. *
  9. *******************************************************************************/
  10.  
  11. #include <cruntime.h>
  12. #include <stdlib.h>
  13. #include <search.h>
  14.  
  15. /***
  16. *char *bsearch() - do a binary search on an array
  17. *
  18. *Purpose:
  19. *       Does a binary search of a sorted array for a key.
  20. *
  21. *Entry:
  22. *       const char *key    - key to search for
  23. *       const char *base   - base of sorted array to search
  24. *       unsigned int num   - number of elements in array
  25. *       unsigned int width - number of bytes per element
  26. *       int (*compare)()   - pointer to function that compares two array
  27. *               elements, returning neg when #1 < #2, pos when #1 > #2, and
  28. *               0 when they are equal. Function is passed pointers to two
  29. *               array elements.
  30. *
  31. *Exit:
  32. *       if key is found:
  33. *               returns pointer to occurrence of key in array
  34. *       if key is not found:
  35. *               returns NULL
  36. *
  37. *Exceptions:
  38. *
  39. *******************************************************************************/
  40.  
  41. void * __cdecl bsearch (
  42.         REG4 const void *key,
  43.         const void *base,
  44.         size_t num,
  45.         size_t width,
  46.         int (__cdecl *compare)(const void *, const void *)
  47.         )
  48. {
  49.         REG1 char *lo = (char *)base;
  50.         REG2 char *hi = (char *)base + (num - 1) * width;
  51.         REG3 char *mid;
  52.         unsigned int half;
  53.         int result;
  54.  
  55.         while (lo <= hi)
  56.                 if (half = num / 2)
  57.                 {
  58.                         mid = lo + (num & 1 ? half : (half - 1)) * width;
  59.                         if (!(result = (*compare)(key,mid)))
  60.                                 return(mid);
  61.                         else if (result < 0)
  62.                         {
  63.                                 hi = mid - width;
  64.                                 num = num & 1 ? half : half-1;
  65.                         }
  66.                         else    {
  67.                                 lo = mid + width;
  68.                                 num = half;
  69.                         }
  70.                 }
  71.                 else if (num)
  72.                         return((*compare)(key,lo) ? NULL : lo);
  73.                 else
  74.                         break;
  75.  
  76.         return(NULL);
  77. }
  78.