home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 300-399 / ff319.lzh / CNewsSrc / cnews.orig.lzh / rna / lib / bsearch.c next >
Text File  |  1989-06-27  |  876b  |  35 lines
  1. /*LINTLIBRARY*/
  2. /*
  3.  * Binary search algorithm, generalized from Knuth (6.2.1) Algorithm B.
  4.  *
  5.  * Written by J. S. Rugaber; rewritten by L. Rosler, Dept. 45175, August, 1981.
  6.  */
  7.  
  8. typedef char *POINTER;
  9.  
  10. POINTER
  11. bsearch(key, base, nel, width, compar)
  12. POINTER    key;            /* Key to be located */
  13. POINTER    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 two_width = width + width;
  19.     POINTER last = base + width * (nel - 1); /* Last element in table */
  20.  
  21.     while (last >= base) {
  22.  
  23.         register POINTER p = base + width * ((last - base)/two_width);
  24.         register int res = (*compar)(key, p);
  25.  
  26.         if (res == 0)
  27.             return (p);    /* Key found */
  28.         if (res < 0)
  29.             last = p - width;
  30.         else
  31.             base = p + width;
  32.     }
  33.     return ((POINTER) 0);        /* Key not found */
  34. }
  35.