bsearch()

Perform a binary search on a sorted array

Synopsis:

#include <stdlib.h>

void *bsearch( const void *key,
               const void *base,
               size_t num,
               size_t width,
               int (*compar)( const void *pkey,
                              const void *pbase) );

Library:

libc

Description:

The bsearch() function performs a binary search on the sorted array of num elements pointed to by base, for an item that matches the object pointed to by key. Each element in the array is width bytes in size.

The comparison function pointed to by compar is called with two arguments pointing to elements in the array. The pkey argument points to the key, and the pbase argument points to an element in the array. The comparison function must return an integer less than, equal to, or greater than zero if the key object is less than, equal to, or greater than the element in the array, respectively.

Returns:

A pointer to a matching member of the array, or NULL if a matching object couldn't be found.

If there are multiple values in the array that match the key, the return value could be any of these duplicate values.

Examples:

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

static const char *keywords[] = {
    "auto",
    "break",
    "case",
    "char",
/*  ... */
    "while"
  };

#define NUM_KW    sizeof(keywords) / sizeof(char *)

int kw_compare( const void *p1, const void *p2 )
{
    const char *p1c = (const char *) p1;
    const char **p2c = (const char **) p2;

    return( strcmp( p1c, *p2c ) );
}

int keyword_lookup( const char *name )
{
    const char **key;

    key = (char const **) bsearch( name, keywords, 
           NUM_KW, sizeof( char * ),  kw_compare );
    if( key == NULL ) return( -1 );

    return key - keywords;
}

int main( void )
{
    printf( "%d\n", keyword_lookup( "case" ) );
    printf( "%d\n", keyword_lookup( "crigger" ) );
    printf( "%d\n", keyword_lookup( "auto" ) );

    return EXIT_SUCCESS;
}

This program produces the following output:

2
-1
0

Classification:

ANSI

See also:

qsort()