BSEARCH(3)                           BSD                            BSEARCH(3)



NAME
     bsearch - binary search a sorted table

SYNOPSIS
     #include <stdlib.h>

     void *bsearch(key, base, nel, size, compar)
     const void *key, *base;
     size_t nel, size;
     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 where a datum
     may be found.  The table must have been sorted previously in increasing
     order, according to a comparison function that you have provided.  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.  size is the size of a table element.  compar is the name of the
     comparison function, which is called with two arguments that point to the
     elements being compared.  The comparison function must return an integer
     less than, equal to, or greater than zero, according to 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
     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 <stdlib.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((void *)(&node),
                            (void *)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)
          void *node1, *node2;
          {
               return (strcmp(
                         ((struct node *)node1)->string,
                         ((struct node *)node2)->string));
          }

SEE ALSO
     qsort(3).

DIAGNOSTICS
     bsearch returns a pointer to a matching element of the array, or a NULL
     pointer if no match is found.  If two elements compare as equal, bsearch
     doesn't specify which element is matched.

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