bsearch()

Updated: April 19, 2023

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

Arguments:

key
The object to search for.
base
A pointer to the first element in the array.
num
The number of elements in the array.
width
The size of an element, in bytes.
compare
A pointer to a user-supplied function that lfind() calls to compare an array element with the key.

The arguments to the comparison function are:

  • pkey — the same pointer as key
  • pbase — a pointer 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.

Library:

libc

Use the -l c option to qcc to link against this library. This library is usually included automatically.

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.

Returns:

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

Note: 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, POSIX 1003.1

Safety:  
Cancellation point No
Interrupt handler Yes
Signal handler Yes
Thread Yes