bsearch(S)                     6 January 1993                     bsearch(S)


 Name

    bsearch - binary search a sorted table

 Syntax


    cc  . . .  -lc


    #include <stdlib.h>

    void *bsearch (key, base, nel, width, compar)
    void *key, *base;
    size_t nel, width;
    int (*compar)();


    SVID Syntax


    #include <search.h>

    char *bsearch (key, base, nel, width, compar)
    void *key, *base;
    size_t nel, width;
    int (*compar)();


 Description

    The bsearch function is a binary search routine.  It returns a pointer
    into a table indicating where a datum may be found.  The table must be
    previously sorted in increasing order according to a provided comparison
    function.  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.  compar is the name of the comparison function,
    which is called with two arguments that point to the elements being com-
    pared.  The function must return an integer less than, equal to, or
    greater than zero if the first argument is to be considered less than,
    equal to, or greater than the second.

 Note

    For compatibility with the System V Interface Definition (SVID), include
    the search.h header file instead of stdlib.h.

 Return value

    The bsearch function returns a pointer to a matching member of the array,
    or a null pointer if no match is found.  If two or more members compare
    equal, which member returned is unspecified.

 Example

    The example below searches a table containing pointers to nodes consist-
    ing 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 mes-
    sage.

    #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((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));
    }


 Diagnostics

    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 com-
    pared.

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

 See also

    hsearch(S), lsearch(S), qsort(S), tsearch(S)

 Standards conformance

    bsearch is conformant with:
    AT&T SVID Issue 2;
    X/Open Portability Guide, Issue 3, 1989;
    ANSI X3.159-1989 Programming Language -- C;
    IEEE POSIX Std 1003.1-1990 System Application Program Interface (API) [C
    Language] (ISO/IEC 9945-1);
    and NIST FIPS 151-1.