bsearch(3)                          CLIX                          bsearch(3)



  NAME

    bsearch - Performs a binary search on a sorted table

  LIBRARY

    Standard C Library (libc.a)

  SYNOPSIS

    #include <stdio.h>

    #include <search.h>

    char *bsearch(
      char *key ,
      char *base ,
      unsigned count ,
      int size ,
      int *compar() );

  PARAMETERS

    key      Points to a datum to be sought.

    base     Points to the first element in the lookup table.

    count    Specifies the number of elements in table.

    size     Specifies the size of a table element.

    compar   Specifies a comparison function.

  DESCRIPTION

    The bsearch() function 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 be previously sorted in ascending
    order according to a provided comparison function.  The key parameter
    points to a datum instance to be sought in the table.  The base parameter
    points to the element at the base of the table.  The count parameter
    specifies the number of elements in the table.  The compar parameter 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 as accordingly the first
    argument is to be considered less than, equal to, or greater than the
    second.

  EXAMPLES

    To search a table containing pointers to nodes consisting of a string and



  2/94 - Intergraph Corporation                                              1

  bsearch(3)                          CLIX                          bsearch(3)



    its length:

    #include <stdio.h>
    #include <search.h>

    #define   TABSIZE   1000

    struct node {            /* these are stored in the table */
         char *string;
         int length;
    };
    struct node tableTABSIZE;     /* 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)
    char *node1, *node2;
    {
         return (strcmp(
                   ((struct node *)node1)->string,
                   ((struct node *)node2)->string));
    }


    The table is ordered alphabetically on the string in the node pointed to
    by each entry.



  2                                              Intergraph Corporation - 2/94

  bsearch(3)                          CLIX                          bsearch(3)



    This code fragment reads in strings and either finds the corresponding
    node and displays the string and its length, or displays an error message.

  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.

  RETURN VALUES

    A NULL pointer is returned if the key cannot be found in the table.

    Although bsearch() is declared as type pointer-to-character, the value
    returned should be cast into type pointer-to-element.

  RELATED INFORMATION

    Functions:  hsearch(3), lsearch(3), qsort(3), tsearch(3)

































  2/94 - Intergraph Corporation                                              3