Searches an array for a specified key

#include <stdlib.h>
void *bsearch ( const void *key , const void *array , size_t n , size_t size ,
               int (*compare )(const void *, const void *));

The bsearch( ) function uses the binary search algorithm to find an element that matches key in a sorted array of n elements of size size. (The type size_t is defined in stdlib.h as unsigned int.) The last argument, compare, gives bsearch( ) a pointer to a function that it calls to compare the search key with any array element. This function must return a value that indicates whether its first argument, the search key, is less than, equal to, or greater than its second argument, an array element to test. For a detailed description of such comparison functions, see qsort( ) in this chapter.

You should generally use qsort( ) before bsearch( ), because the array must be sorted before searching. This step is necessary because the binary search algorithm tests whether the search key is higher or lower than the middle element in the array, then eliminates half of the array, tests the middle of the result, eliminates half again, and so forth. If you define the comparison function for bsearch( ) with identical types for its two arguments, then qsort( ) can use the same comparison function.

The bsearch( ) function returns a pointer to the first array element found that matches the search key. If no matching element is found, bsearch( ) returns a null pointer.

Example

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

typedef struct  { unsigned long id;
                  int data;
                } record ;

int main( )
{
  int id_cmp(const void *s1, const void *s2); //Declare comparison function

  record recordset[ ] = { {3, 5}, {5, -5}, {4, 10}, {2,  2}, {1, -17} };
  record querykey;
  record *found = NULL;
  int recordcount = sizeof( recordset ) / sizeof ( record );

  printf( "Query record number: ");
  scanf( "%lu", &querykey.id );

  printf( "\nRecords before sorting:\n\n"
          "%8s %8s %8s\n", "Index", "ID", "Data" );

  for ( int i = 0; i < recordcount ; i++ )
    printf( "%8d %8u %8d\n", i, recordset[i].id, recordset[i].data );

  qsort( recordset, recordcount, sizeof( record ), id_cmp );

  printf( "\nRecords after sorting:\n\n"
          "%8s %8s %8s\n", "Index", "ID", "Data" );
  for ( int i = 0; i < recordcount ; i++ )
    printf( "%8d %8u %8d\n", i, recordset[i].id, recordset[i].data );

  found = (record *) bsearch( &querykey, recordset, recordcount,
                             sizeof( record ), id_cmp  );
  if ( found == NULL )
    printf( "No record with the ID %lu found.\n", querykey.id );
  else
    printf( "The data value in record %lu is %d.\n",
            querykey.id, found->data );

} // End of main( ).

int id_cmp(const void *s1, const void *s2)
/* Compares records by ID, not data content. */
{
  record *p1 = (record *)s1;
  record *p2 = (record *)s2;

  if      ( p1->id <  p2->id ) return -1;
  else if ( p1->id == p2->id ) return  0;
  else return 1;
}

This example produces the following output:

Query record number: 4

Records before sorting:

   Index       ID     Data
       0        3        5
       1        5       -5
       2        4       10
       3        2        2
       4        1      -17

Records after sorting:

   Index       ID     Data
       0        1      -17
       1        2        2
       2        3        5
       3        4       10
       4        5       -5
The data value in record 4 is 10.

See Also

qsort( )