bsearch(3C)                                                     bsearch(3C)

NAME
     bsearch - binary search a sorted table

SYNOPSIS
     #include <stdlib.h>

     void *bsearch(const void *key, const void *base, sizet nel,
           sizet size, int (*compar)(const void *, const void *));

DESCRIPTION
     bsearch() is a binary search routine generalized from Knuth (6.2.1)
     Algorithm B. It returns a pointer into a table (an array) indicating
     where data may be found. It returns a null pointer if the data cannot
     be found. key points to a data instance 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. size is the number of bytes in each element.
     The function pointed to by compar is called with two arguments that
     point to key and an element of the table (in this order). The function
     must return an integer less than, equal to, or greater than 0 as
     accordingly the first argument is to be considered less than, equal
     to, or greater than the second. The table must contain the following
     elements: first all elements that are less than key, then all elements
     that are equal to key, and finally all elements that are greater than
     key.

EXAMPLE
     This example searches a table containing 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 program 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 <stdlib.h>
     #include <string.h>

     struct node {                 /* these are stored in the table */
           char *string;
           int length;
     };
     static struct node table[] =  /* table to be searched */
     {
          { "asparagus", 10 },
          { "beans", 6 },
          { "tomato", 7 },
          { "watermelon", 11 },
     };

     main()
     {
           struct node *nodeptr, node;



Page 1                       Reliant UNIX 5.44                Printed 11/98

bsearch(3C)                                                     bsearch(3C)

           /* routine to compare 2 nodes */
           static int nodecompare(const void *, const void *);
           char strspace[20];   /* space to read string into */
           node.string = strspace;
           while (scanf("%20s", node.string) != EOF) {
                   nodeptr = bsearch( &node,
                              table, sizeof(table)/sizeof(struct node),
                              sizeof(struct node), nodecompare);
                   if (nodeptr != NULL) {
                           (void) printf("string = %20s, length = %d\n"
                                   nodeptr->string, nodeptr->length);
                   } else {
                           (void)printf("not found: %20s\n", node.string)
                   }
           }
           return(0);
     }

     /* routine to compare two nodes based on an  */
     /* alphabetical ordering of the string field */
     static int
     nodecompare(const void *node1, const void *node2)
     {
           return (strcmp(
                           ((const struct node *)node1)->string,
                           ((const struct node *)node2)->string));
     }

RESULT
     A null pointer is returned if the key cannot be found in the table;
     otherwise, a pointer is returned, pointing to the required place in
     the table.

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

     The comparison function need not compare every byte, so arbitrary data
     may be contained in the elements in addition to the values being com-
     pared.

     If the number of elements in the table is less than the size reserved
     for the table, nel should be the lower number.

SEE ALSO
     hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C).








Page 2                       Reliant UNIX 5.44                Printed 11/98