bsearch(3C)                                           bsearch(3C)



NAME
     bsearch - performs a binary search on 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
     indicating where a datum may be found.  The table must be
     previously sorted in increasing order according to a
     provided comparison function.  The pointer key points to a
     datum 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; 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 arguments that point to the elements being compared.
     The function 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 */
           .
           .
           .



January 1992                                                    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);
        }


STATUS MESSAGES AND VALUES
     A NULL pointer is returned if the key cannot be found 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, 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 type pointer-to-element.

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





2                                                    January 1992

bsearch(3C)                                           bsearch(3C)



     Donald Knuth, The Art of Computer Programming: Volume 3,
     Sorting and Searching.





















































January 1992                                                    3