BSEARCH(S)               XENIX System V                BSEARCH(S)



     Name
          bsearch - Performs a binary search.

     Syntax
          #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 into a table
          indicating the location at which a datum may be found.  The
          table must be previously sorted in increasing order
          according to a provided comparison function, compar.  key is
          a pointer to the datum to be located in the table.  base is
          a pointer to the elements at the base of the table.  nel is
          the number of elements in the table.  width is the size of
          an element in bytes.  compar is the name of the comparison
          routine.  It is called with two arguments which are pointers
          to the elements being compared.  The routine must return an
          integer less than, equal to, or greater than zero, depending
          on whether the first argument is to be considered less than,
          equal to, or greater than the second.

     Example
          The example below searches a table containing pointers to
          nodes. The nodes consist of a string and its length.  The
          table is ordered alphabetically on the string in the node
          pointed to by each entry.

          The following code fragment reads in strings and either
          finds the corresponding node and prints out the string and
          its length, or prints an error message, (as shown on the
          next page).

















     Page 1                                           (printed 8/7/87)

     BSEARCH(S)               XENIX System V                BSEARCH(S)



               #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 */
                    .
                    .
                    .
               {
                    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 *nodel, *node2;
               {
                    return strcmp(nodel->string, node2->string);
               }

     See Also
          hsearch(S), lsearch(S), qsort(S), tsearch(S)









     Page 2                                           (printed 8/7/87)

     BSEARCH(S)               XENIX System V                BSEARCH(S)



     Diagnostics
          If the key cannot be found in the table, a NULL (0) pointer
          is returned.

     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 arbitrary 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 pointer-to-element.











































     Page 3                                           (printed 8/7/87)