home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume23 / smiley / part01 / bsearch.c next >
Encoding:
C/C++ Source or Header  |  1991-10-22  |  897 b   |  36 lines
  1. /*
  2.  * A binary search generalized from Knuth (6.2.1) Algorithm B just
  3.  * like the AT&T man page says...
  4.  *
  5.  * Written by reading the System V Interface Definition, not the code.
  6.  *
  7.  * Totally public domain.
  8.  */
  9. /*LINTLIBRARY*/
  10.  
  11. char *bsearch(key, base, nel, width, compar)
  12. char    *key;            /* Key to be located */
  13. char    *base;            /* Beginning of table */
  14. unsigned nel;            /* Number of elements in the table */
  15. unsigned width;            /* Width of an element (bytes) */
  16. int    (*compar)();        /* Comparison function */
  17. {
  18.     int doublewidth = width + width;
  19.  
  20.     char *last = base + width * (nel - 1);
  21.  
  22.     while (last >= base)
  23.     {
  24.     register char *p = base + width * ((last - base)/doublewidth);
  25.     register int cmp = (*compar)(key, p);
  26.  
  27.     if (cmp == 0)
  28.         return (p);            /* aha, we found it! */
  29.     if (cmp < 0)
  30.         last = p - width;
  31.     else
  32.         base = p + width;
  33.     }
  34.     return ((char *) 0);        /* didn't find it */
  35. }
  36.