BSEARCH(3C)                          SysV                          BSEARCH(3C)



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)() (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 indicating where a datum
     may be found.  The table must have been sorted previously in increasing
     order, according to a comparison function, compar.  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
     cc(1), hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C).

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
     To be compatible with traditional C usage, make bsearch return the type
     pointer-to-character by compiling your program with the

          -A nansi

     option (see cc(1)) and inserting the directive

          #define _CLASSIC_TYPES

     before any #include directives in your program.  In that case, the value
     returned should be cast into 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
     compared.