home *** CD-ROM | disk | FTP | other *** search
/ Microsoft Programmer's Library 1.3 / Microsoft-Programers-Library-v1.3.iso / sampcode / alde_c / misc / lib / dlibssrc / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-07-14  |  1.2 KB  |  41 lines
  1. #include <stdio.h>
  2.  
  3. int    _bsearch;    /* index of element found, or where to insert */
  4.  
  5. char *bsearch(key, base, num, size, cmp)
  6. register char *key;        /* item to search for */
  7. register char *base;        /* base address */
  8. int num;            /* number of elements */
  9. register int size;        /* element size in bytes */
  10. register int (*cmp)();        /* comparison function */
  11. /*
  12.  *    Perform a binary search for <key> on the sorted data at <base>.
  13.  *    <num>, <size> and <cmp> are like the corresponding parameters
  14.  *    to qsort().  A pointer to the matching element is returned for
  15.  *    success, or NULL for failure.  The global variable "_bsearch"
  16.  *    will contain the index of either the matching element, or the
  17.  *    place where <key> value should be inserted.  The use of "_bsearch"
  18.  *    is not supported by many implementations of bsearch().
  19.  */
  20. {
  21.     register int a, b, c, dir;
  22.  
  23.     a = 0;
  24.     b = num - 1;
  25.     while(a <= b) {
  26.         c = (a + b) >> 1;    /* == ((a + b) / 2) */
  27.         if (dir = (*cmp)((base + (c * size)), key)) {
  28.             if (dir > 0)
  29.                 b = c - 1;
  30.             else /* (dir < 0) */
  31.                 a = c + 1;
  32.         }
  33.         else {
  34.             _bsearch = c;
  35.             return(base + (c * size));
  36.         }
  37.     }
  38.     _bsearch = b;    
  39.     return(NULL);
  40. }
  41.