bsearch() -- General Function (libc)

Search an array
#include <stdlib.h>
char *bsearch(key, array, number, size, comparison)
char *key, *array;
size_t number, size;
int (*comparison)();

bsearch() searches  a sorted array  for a given  item.  item points  to the
object  sought.  array  points to  the  base of  the array;  it has  number
elements, each  of which is size  bytes long.  Its elements  must be sorted
into ascending order before it is searched by bsearch().

comparison points to the function that compares array elements.  comparison
must return zero if its arguments  match, a number greater than zero if the
element pointed to by arg1 is  greater than the element pointed to by arg2,
and a number less than zero  if the element pointed to by arg1 is less than
the element pointed to by arg2.

bsearch() returns a  pointer to the array element that  matches item. If no
element  matches  item, then  bsearch()  returns NULL.   If  more than  one
element within array matches item, which element is matched is unspecified.

Example

This example uses bsearch() to translate English into ``bureaucrat-ese''.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct syntab {
    char *english, *bureaucratic;
} cdtab[] = {
/* The left column is in alphabetical order */

    "affect",  "impact",
    "after",   "subsequent to",
    "broke",   "revenue shortfall",
    "building","physical facility",
    "call",    "refer to as",
    "do",      "implement",

    "false",   "inoperative",
    "finish",  "finalize",
    "first",   "initial",
    "full",    "in-depth",
    "help",    "facilitate",

    "idiot",   "elected representative",
    "kill",    "terminate with extreme prejudice",
    "lie",     "inoperative statement",
    "order",   "prioritize",
    "talk",    "interpersonal communication",
    "then",    "at that point in time",
    "use",     "utilize"
};

int
comparator(key, item)
char *key;
struct syntab *item;
{
    return(strcmp(key, item->english));
}

main()
{
    struct syntab *ans;
    char buf[80];

    for(;;) {
               printf("Enter an English word: ");
               fflush(stdout);

               if(gets(buf) || !strcmp(buf, "quit") == NULL)
               break;

               if((ans = bsearch(buf, (char *)cdtab,
                sizeof(cdtab)/ sizeof(struct syntab),
                sizeof(struct syntab),
                comparator)) == NULL)
               printf("%s not found\n");

               else
               printf("Don't say \"%s\"; say \"%s\"!\n",
                ans->english, ans->bureaucratic);
    }

    return(EXIT_SUCCESS);
}

See Also

libc,
qsort(),
stdlib.h
ANSI Standard, §7.10.6.2
POSIX Standard, §8.1

Notes

The name  bsearch implies that  this function performs a  binary search.  A
binary search looks at the midpoint  of the array, and compares it with the
element being sought.  If that element  matches, then the work is done.  If
it does not, then bsearch() checks the midpoint of either the upper half of
the array or of the lower  half, depending upon whether the midpoint of the
array is  larger or smaller than the item  being sought.  bsearch() bisects
smaller and smaller  regions of the array until it  either finds a match or
can bisect no further.

It  is important  that the  input array  be sorted,  or bsearch()  will not
function correctly.

© 2012 by Stephen A. Ness