home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume24 / mkid2 / part01 / bsearch.c < prev    next >
C/C++ Source or Header  |  1991-10-09  |  692b  |  37 lines
  1. /* Copyright (c) 1986, Greg McGary */
  2. static char sccsid[] = "@(#)bsearch.c    1.1 86/10/09";
  3.  
  4. char *bsearch();
  5.  
  6. /*
  7.     Binary search -- from Knuth (6.2.1) Algorithm B
  8. */
  9. char *
  10. bsearch(key, base, nel, width, compar)
  11.     char        *key;
  12.     register char    *base;
  13.     unsigned int    nel;
  14.     int        width;
  15.     int        (*compar)();
  16. {
  17.     register char    *last;
  18.     register char    *position;
  19.     register int    result;
  20.     int        width2;
  21.  
  22.     width2 = width * 2;
  23.     last = &base[width * (nel - 1)];
  24.  
  25.     while (last >= base) {
  26.         position = &base[width * ((last - base)/width2)];
  27.         
  28.         if ((result = (*compar)(key, position)) == 0)
  29.             return position;
  30.         if (result < 0)
  31.             last = position - width;
  32.         else
  33.             base = position + width;
  34.     }
  35.     return (char *)0;
  36. }
  37.