4.3BSD - /usr/src/new/spms/src/bin/pfind/binary.c

   1: /* $Header$ */
   2: 
   3: /*
   4:  * Author: Peter J. Nicklin
   5:  */
   6: #include "yesno.h"
   7: 
   8: static char **STRINGS;          /* pointer array containing strings */
   9: static int NSTRINGS;            /* number of strings in STRINGS */
  10: 
  11: /*
  12:  * bininit() initializes and sorts the STRINGS pointer array.
  13:  */
  14: void
  15: bininit(argc, argv)
  16:     int argc;
  17:     char **argv;
  18: {
  19:     int qsort();            /* quicker sort */
  20:     int strpcmp();          /* pointed-to string comparison */
  21: 
  22:     NSTRINGS = argc;
  23:     STRINGS = argv;
  24:     qsort((char *) STRINGS, NSTRINGS, sizeof(char *), strpcmp);
  25: }
  26: 
  27: 
  28: 
  29: /*
  30:  * binsearch() returns integer YES if string is found in sorted pointer
  31:  * array STRINGS, otherwise NO. Uses binary search.
  32:  */
  33: binsearch(string)
  34:     char *string;           /* string to be matched */
  35: {
  36:     int comp;           /* compare string values */
  37:     int high;           /* upper limit of array */
  38:     int low;            /* lower limit of array */
  39:     int mid;            /* middle of search range */
  40:     int strcmp();           /* string comparison */
  41: 
  42:     low = 0;
  43:     high = NSTRINGS - 1;
  44:     while (low <= high)
  45:         {
  46:         mid = (low+high) / 2;
  47:         if ((comp = strcmp(string, STRINGS[mid])) < 0)
  48:             high = mid - 1;
  49:         else if (comp > 0)
  50:             low = mid + 1;
  51:         else
  52:             return(YES);
  53:         }
  54:     return(NO);
  55: }
  56: 
  57: 
  58: 
  59: /*
  60:  * strpcmp() compares strings in a pointer array. Returns whatever strcmp()
  61:  * returns.
  62:  */
  63: static int
  64: strpcmp(s1, s2)
  65:     char **s1;
  66:     char **s2;
  67: {
  68:     int strcmp();           /* string comparison */
  69: 
  70:     return(strcmp(*s1, *s2));
  71: }

Defined functions

Defined variables