home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / news / cnews.tar / readnews / bsearch.c < prev    next >
Text File  |  1993-07-17  |  824b  |  31 lines
  1. /*
  2.  * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
  3.  *
  4.  * Written by J. S. Rugaber; rewritten by L. Rosler, Dept. 45175, August, 1981.
  5.  */
  6. char *
  7. search(key, base, nel, width, compar)
  8. char *key;            /* Key to be located */
  9. char *base;            /* Beginning of table */
  10. unsigned nel;            /* Number of elements in the table */
  11. unsigned width;            /* Width of an element (bytes) */
  12. int    (*compar)();        /* Comparison function */
  13. {
  14.     int two_width = width + width;
  15.     char *last = base + width * (nel - 1); /* Last element in table */
  16.  
  17.     while (last >= base) {
  18.  
  19.         register char *p = base + width * ((last - base)/two_width);
  20.         register int res = (*compar)(key, p);
  21.  
  22.         if (res == 0)
  23.             return (p);    /* Key found */
  24.         if (res < 0)
  25.             last = p - width;
  26.         else
  27.             base = p + width;
  28.     }
  29.     return ((char *) 0);        /* Key not found */
  30. }
  31.