bsearch(3C)                                           bsearch(3C)



     NAME
          bsearch - binary search a sorted table

     SYNOPSIS
          #include <search.h>

          char *bsearch(key, base, nel, width, compar)
          char *key;
          char *base;
          unsigned nel, width;
          int (*compar)();

     DESCRIPTION
          bsearch is a binary search routine generalized from Knuth
          (6.2.1) Algorithm B.  It returns a pointer to a table indi-
          cating where a datum may be found.  The table must be previ-
          ously sorted in increasing order according to a provided
          comparison function.  The pointer key points to a datum in-
          stance to be sought in the table; base points to the element
          at the base of the table; nel is the number of elements in
          the table; width is the width of an element in bytes (the
          sizeof (*key) should be used for width); compar is the name
          of the comparison function which is called with two argu-
          ments that point to the elements being compared.  The func-
          tion must return an integer less than, equal to, or greater
          than 0, depending on whether or not the first argument is to
          be considered less than, equal to, or greater than the
          second.

     EXAMPLES
          The example following searches a table that contains
          pointers to nodes consisting of a string and its length.
          The table is ordered alphabetically on the string in the
          node pointed to by each entry.

          This code fragment reads in strings and either finds the
          corresponding node and prints out the string and its length,
          or prints an error message.

          #include <stdio.h>
          #include <search.h>

          #define   TABSIZE   1000

          struct node {  /* these are stored in the table */
             char *string;
             int length;
          };
          struct node table[TABSIZE];  /* table to be searched */
             .
             .
             .



     April, 1990                                                     1

     bsearch(3C)                                           bsearch(3C)



          {
             struct node /*node_ptr, node;
             int node_compare( );  /* routine to compare 2 nodes */
             char str_space[20];   /* space to read string into */
             .
             .
             .
             node.string = str_space;
             while (scanf("%s", node.string) != EOF) {
                node_ptr = (struct node *)bsearch((char *)(&node),
                      (char *)table, TABSIZE,
                      sizeof(struct node), node_compare);
                if (node_ptr != NULL) {
                   (void)printf("string = %20s, length = %d\n",
                      node_ptr->string, node_ptr->length);
                } else {
                   (void)printf("not found: %s\n", node.string);
                }
             }
          }
          /*
             This routine compares two nodes based on an
             alphabetical ordering of the string field.
          */
          int
          node_compare(node1, node2)
          struct node *node1, *node2;
          {
             return strcmp(node1->string, node2->string);
          }


     NOTES
          The pointers to the key and the element at the base of the
          table should be of type pointer-to-element, and cast to type
          pointer-to-character.

          The comparison function need not compare every byte, so ar-
          bitrary data may be contained in the elements in addition to
          the values being compared.

          Although declared as type pointer-to-character, the value
          returned should be cast into type pointer-to-element.

     RETURN VALUE
          A NULL pointer is returned if the key cannot be found in the
          table.

     SEE ALSO
          hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C).
          Donald Knuth, The Art of Computer Programming: Volume 3,
          Sorting and Searching.



     2                                                     April, 1990