bsearch()

perform a binary search of 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) );

Description:

The bsearch() function performs a binary search of a 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 that point to elements in the array. The first argument pkey points to the same object pointed to by key. The second argument pbase points to a 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 the matching member of the array, or NULL if a matching object couldn't be found.

If there are multiple values in the array that are equal to the key, the return value is not necessarily the first occurrence of a matching value when the array is searched linearly.

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;
  }

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

This program produces the following output:

2
-1
0

Classification:

ANSI

See also:

lfind(), lsearch(), qsort()