C programming bsearch stdlib.h


In C programming the <stdlib.h> bsearch function searches for a particular element in an array.The declaration of the function is given below.

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

Parameters:
key -The element to search for in the array.

base -The first address of the sorted array in which the element is to be searched for.

nmemb -Number of elements in the array.

size -Size of each element of the array.

compar -A function that will be used to find the ‘key’ in the array.

Return type
void* -An address to the element found in the array.If the element does not exist in the array NULL is returned.

Description

The ‘bsearch‘ function is not a standalone function that can search for a specific element in an array.It requires that we pass a function which can find the element in the array.We pass this function as the fifth argument when ‘bsearch’ is called:namely the ‘compar’ function.But,how do we define such function?

There is certain prerequisite rules the function must follow to be passed as the 5th argument must follow.It must return an ‘int’ type value.And say that two arguments indentifier are ‘arg1’ and ‘arg2’.The declaration of ‘compar’ function will look like this(It is not necessary that you name the function ‘compar’,you can name it whatever you want).

int compar( const void* arg1, const void* arg2);

The value returned must follow the rule describe below.

If arg1 is less than arg2less than zero is returned
If arg1 is equal to arg2zero is returned
If arg1 is greater than arg2value greater than 0 is returned

A code example is given below,note the ‘compar’ fucntion.

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

typedef struct {
char c[10];
} String ;

int compar( const void* arg1, const void* arg2 )
{
return strcmp( (((String *)arg1)->c) , (((String *)arg2)->c) ); //the ‘strcmp’ function compare two string
}

int main( )
{
String st[]={“atexit” , “calloc” , “free” , “rand” , “srand” };

char key[]=”rand” ;

void *result=bsearch( &key ,   ///the element to search for in the ‘st’ array
  st ,   ///the array in which the element is to be searched for
  sizeof(st)/sizeof(String) ,  ///number of elements in ‘st’ array,compute to 5
  sizeof(String) ,  ///size of the single element in ‘st’ array
  compar );   ///the function which searches for ‘key’ in ‘st’ array

if( result )   //check if result is NULL
{ //if not NULL
printf(“%s” , ((char*)result)) ; //cast result to ‘char*’ and output the value
}
else  //If NULL
  printf( “String not found”) ;

getchar( ) ;
return 0 ;
}

Output

rand

Since ‘rand’ exits in ‘st’ array it is printed out.





Some points to note about ‘bsearch’ function:

i) The ‘compar’ or some other ‘compar’ equivalent function must only return ‘int’ type,if it return any other type it is an error.For example try implementing the function shown below in the above program.

Code example

float compar( const void* arg1, const void* arg2 )
{
return strcmp( *(const char**)arg1 , *(const char**)arg2 );
}

In Code::block you will get the error as “invalid conversion from ‘float (*)(const void*, const void*)’ to ‘int (*)(const void*, const void*)’“.


ii)If the ‘compar’ find two matching elements in the array,which one address is returned is undefined.


iii) If the ‘compar’ function throws an exception ,the ‘bsearch’ is allowed to propagate them.


iv) The array in which the element to be searched for should be sorted in ascending order.If the array elements are sorted in descending order or the elements are distributed randomly then the ‘compar’ function cannot find the elements.

Code example :The code example uses ‘compar’ function from the first program of this post.

int main( )
{
String ar[]={ “numeric” , “algorithm” , “map” , “memory” };

char s[]=”map” ;

void *result=bsearch( &s ,
  ar ,
  sizeof(ar)/sizeof(String) ,
  sizeof(String) ,
  compar );

if( result )
{
printf(“%s” , (char*)result ) ;
}
else
  printf( “String not found”);

getchar( );
return 0;

Output

String not found

Even though ‘map’ is present in ‘ar’ array the ‘compar’ cannot match it because the ‘ar’ elements are not sorted.So do remember to sort the array elements if you plan on using ‘bsearch’ to find value in the array.


Related Link

->C++ cstdlib qsort