home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume26 / mytinfo / part01 / bsearch.c < prev    next >
C/C++ Source or Header  |  1992-12-26  |  2KB  |  98 lines
  1. /*
  2.  * bsearch.c
  3.  *
  4.  * This is something I found on watmath. I've made some minor changes for use
  5.  * in this package.
  6.  *
  7.  * 92/06/04 11:35:15
  8.  */
  9.  
  10. #if 0
  11. #ifndef lint
  12. static char *RCSid = "$OHeader: /usr/mfcf/src/accounts/libuw/RCS/bsearch.c,v 1.1 88/06/11 20:41:48 root Exp $";
  13. #endif
  14. #endif
  15.  
  16. #include "defs.h"
  17.  
  18. #ifdef USE_MYBSEARCH
  19.  
  20. #ifdef USE_SCCS_IDS
  21. static char const SCCSid[] = "@(#) mytinfo bsearch.c 3.4 92/06/04 public domain, By Ross Ridge";
  22. #endif
  23.  
  24. #ifdef USE_SHORT_BSEARCH
  25. #define fast_int short
  26. #else
  27. #define fast_int mysize_t
  28. #endif
  29.  
  30. /*
  31.  * bsearch - find an element of a sorted vector
  32.  *
  33.  *    found = bsearch(key, array, dimension, width, compare)
  34.  *        returns a pointer to the specified element in the array,
  35.  *        or (char*)0 if the element can't be found.
  36.  *    key
  37.  *        pointer to the element to be searched for in the array
  38.  *    array
  39.  *        address of an array of elements
  40.  *    dimension
  41.  *        number of elements in the array
  42.  *    width
  43.  *        sizeof(type) of each element
  44.  *    compare
  45.  *        pointer to a function taking (char *) pointers to two elements
  46.  *        and returning <0, 0, or >0 as the first element comes before,
  47.  *        at, or after the second element.  A compare function is provided
  48.  *        for comparing strings.
  49. */
  50. #if 0
  51. /*
  52.  * $OLog:    bsearch.c,v $
  53.  * Revision 1.1  88/06/11  20:41:48  root
  54.  * Initial revision
  55.  * 
  56. */
  57. #endif
  58.  
  59.     static anyptr
  60. bsearch(key, array, dimension, iwidth, compare)
  61.     anyptr key;
  62.     anyptr array;
  63.     int dimension;
  64.     mysize_t iwidth;
  65.     compar_fn compare;
  66. {
  67.     register fast_int start;   /* offset to start of current interval */
  68.     register fast_int end;     /* offset to end+1 of current interval */
  69.     register fast_int middle;  /* offset to middle of current interval */
  70.     auto int status;
  71.     register fast_int width;
  72.  
  73.     width = iwidth / sizeof(char);
  74.  
  75.     start = 0;
  76.     middle = 0;
  77.     end = dimension;
  78.  
  79.     while (start < end) {
  80.  
  81.         middle = (start + end) / 2;
  82.  
  83.         status = (*compare)(key, ((char *)array + middle*width));
  84.  
  85.         if (status < 0)
  86.             end = middle;
  87.  
  88.         else if (status > 0)
  89.             start = middle + 1;
  90.  
  91.         else return (anyptr)(((char *)array) + middle*width);
  92.     }
  93.  
  94.     return  0;
  95. }
  96.  
  97. #endif /* USE_MYBSEARCH */
  98.