bsearch

Performs a binary search. It searches an array of sorted objects for a specified object.

Format

#include  <stdlib.h>

void *bsearch  (const void *key, const void *base,
               size_t nmemb, size_t size, int
               (*compar)
               (const void *, const void *));

Arguments

key

A pointer to the object to be sought in the array. This pointer should be of type pointer-to-object and cast to type pointer-to- void.

base

A pointer to the initial member of the array. This pointer should be of type pointer-to-object and cast to type pointer-to- void.

nmemb

The number of objects in the array.

size

The size of an object, in bytes.

compar

A pointer to the comparison function.

Description

Two arguments are passed to the comparison function pointed to by compar. The two arguments point to the objects being compared. Depending on whether the first argument is less than, equal to, or greater than the second argument, the comparison function must return an integer less than, equal to, or greater than 0.

It is not necessary for the comparison function (compar) to compare every byte in the array. Therefore, the objects in the array can contain arbitrary data in addition to the data being compared.

Since it is declared as type pointer-to-void, the value returned must be cast or assigned into type pointer-to-object.

Return Values

x	A pointer to the matching member of the array or a null pointer if no match is found.
NULL	Indicates that the key cannot be found in the array.

Example

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

#define SSIZE 30

extern int compare();   /* function prototype for comparison function */

int array[SSIZE] = {30, 1, 29, 2, 28, 3, 27, 4, 26, 5, 24, 6, 23, 7, 22, 8,
                    21, 9, 20, 10, 19, 11, 18, 12, 17, 13, 16, 14, 15, 25};

/*
 *  This program takes an unsorted array, sorts it using qsort, and then
 *  calls bsearch for each element in the array, making sure that bsearch
 *  returns the correct element.
 */

main()
{
    int i;
    int failure = FALSE;
    int *rkey;

    qsort(array, SSIZE, sizeof(array[0]), &compare);

    /* search for each element */
    for (i = 0; i < SSIZE - 1; i++)
        {
        /* search array element i */
        rkey = bsearch((array+i), array, SSIZE, sizeof(array[0]), &compare);
        /* check for successful search */
        if (&array[i] != rkey)
          {
           printf("Not in array, array element %d\n", i);
           failure = TRUE;
           break;
          }
        }
    if (!failure)
        printf("All elements successfully found!\n");
}

/*
 *  Simple comparison routine.
 *
 *  Returns:  = 0 if a == b
 *            < 0 if a < b
 *            > 0 if a > b
 */
int compare(int *a, int *b)
{
    return (*a - *b);
}