home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 308_01 / bfind.c < prev    next >
Text File  |  1990-06-17  |  3KB  |  121 lines
  1.  
  2. /*
  3.     HEADER:         CUG308;
  4.     TITLE:          binary search of sorted List;
  5.  
  6.     DATE:           5/6/90;
  7.     VERSION:        2.01;
  8.     FILENAME:       BFIND.C;
  9.     SEE-ALSO:       BFIND.H, LIST.DOC, LIST.H, LIST.C;
  10.  
  11.     USEAGE:         "Compile to .obj and link with list.obj and
  12.             your main program";
  13.  
  14.     REQUIREMENTS:   LIST.OBJ V. 2.0 or higher, LIST.H, BFIND.H;
  15.  
  16.     AUTHOR:         Michael Kelly
  17.             254 Gold St. Boston Ma. 02127;
  18.     COPYRIGHT:    May be used freely if authorship is acknowledged;
  19. */
  20.  
  21.  
  22. /*
  23.  *  BFIND
  24.  */
  25.  
  26. #include <stddef.h>
  27. #include "bfind.h"
  28.  
  29.  
  30. /*
  31.  *  routine to binary search sorted List ( see list.h )
  32.  *
  33.  *  requires:    List pointer to a List that has been sorted with sort()
  34.  *        List member function
  35.  *
  36.  *  warning:    the current list.compare() function should be the same
  37.  *        as, or consistent with, the one used for the sort
  38.  *
  39.  *        ( see list.chgcompare() in "list.doc" file )
  40.  *
  41.  *  returns:    1 if item found -- item is now "current"
  42.  *
  43.  *        0 if not found -- "current" item undefined
  44.  */
  45. int bfind(List *list, void *item)
  46. {
  47.     size_t i;                   /* loop counter                     */
  48.     size_t gap;            /* gap used to halve search path      */
  49.     const int opt = 3;        /* use this for performance tuning      */
  50.     const int termcount = 2;    /* for ending "forever" while loop      */
  51.  
  52.     enum direction{ left, right } direc;      /* direction to step     */
  53.     int (*step[2])();                /* to step through list  */
  54.     int dif;                                    /* comparison result     */
  55.     int count = 0;                /* count of single steps */
  56.  
  57.  
  58.     if(! list->entries)
  59.     return 0;
  60.  
  61.     if(list->entries < opt)
  62.     return(list->find(list->id, item));
  63.  
  64.     step[left] = list->prev;
  65.     step[right] = list->next;
  66.  
  67.     list->first(list->id);
  68.  
  69.     /*
  70.      *  if item less than smallest item in list,
  71.      *  dif is < 0 (!dif == 0 or not found);
  72.      *  if item == smallest item in list,
  73.      *  dif is 0 (!dif == 1 or found);
  74.      *  --  results erroneous
  75.      *  if list not sorted in ascending order
  76.      */
  77.     if((dif = list->cmpitem(list->id, item)) < 1)
  78.     return !dif;
  79.  
  80.     list->last(list->id);
  81.  
  82.     /*
  83.      *  compare to largest item in list
  84.      */
  85.     if((dif = list->cmpitem(list->id, item)) > -1)
  86.     return !dif;
  87.  
  88.     /*
  89.      *  if not found at either end of list,
  90.      *  partition the list by shifting the
  91.      *  number of entries right one bit, then
  92.      *  round odd numbers up after shift so
  93.      *  we're not short of middle
  94.      */
  95.     gap = (list->entries >> 1) + (list->entries & 1);
  96.     direc = left;
  97.  
  98.     while(gap)  {       /*  forever  */
  99.     for(i=0;i<gap;i++)
  100.         step[direc](list->id);
  101.  
  102.     if(!(dif = list->cmpitem(list->id, item)))
  103.         return 1;
  104.     else if(dif < 0)
  105.         direc = left;
  106.     else
  107.         direc = right;
  108.  
  109.     /*
  110.      *  quit if not found after a couple of single steps
  111.      */
  112.     if(gap == 1)
  113.         ++count;
  114.     if(count == termcount)
  115.         break;
  116.  
  117.     gap = (gap >> 1) + (gap & 1);
  118.     }
  119.     return 0;
  120. }
  121.