C Reference function bsearch()

The function bsearch() of the stdlib.h is used to do a binary search in an array.

Usage of bsearch():

void * bsearch ( const void * key, const void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

It is searching for a given key in the array that is pointed to by base. Base is formed by the number of elements (num). Each element has a size of size bytes. The function will return a void* pointer to the first element that is matching the search key. The function compares each element to the key by calling the comparator.

The values in the base array need to be pre-sorted in ascending order (because it is a binary search.)

Parameters:

The parameter key is a pointer to the object that is serving as the key for the search. Note that it is type-casted as a void*.

The parameter base is a pointer to the first object of the array. Note that it is type-casted as a void*.

The parameter num is the number of elements in the array that is pointed by base.

The parameter size gives the size in bytes of each element in the array.

The comparator parameter is a function that compares two elements of the array. The prototype of the function comparator should look like this:

int comparator ( const void * element1, const void * element2 );

A general comparator function can look like this:

int compare_a_type(const void * a, const void * a)
{
  if ( *(AType*)a >  *(AType*)b ) return 1;
  if ( *(AType*)a == *(AType*)b ) return 0;
  if ( *(AType*)a <  *(AType*)b ) return -1;
}

If you want to compare C strings you can directly use the strcmp as the comparator.
If the entry is found that matches the search key then a pointer is returned.
If no match is found then a NULL pointer is returned.

Return value:

None.

Source code example of bsearch() using strcmp to compare C strings:

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

char str_array[][20] = {"gh","ef","cd","ab"};

int main ()
{
	char * ptr_item;
	char searchkey[20];

	printf ("Enter a searchkey: ");
	scanf ("%s", &searchkey);

	/* sort the elements of the array */
	qsort(str_array,4,20,(int(*)(const void*,const void*)) strcmp);

	/* search for the searchkey */
	ptr_item = (char*)
		bsearch (searchkey,str_array,4,20,(int(*)
		(const void*,const void*)) strcmp);

	if (ptr_item!=NULL)
		printf ("%s found in the array.\n",ptr_item);
	else
		printf ("%s not found in the array.\n",searchkey);
	return 0;
}

Source code example of bsearch() with own comparator:

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

int compare_integers (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

/*Note that the array is already sorted!*/
int my_array[] = { 5, 10, 15, 20, 25, 30 };

int main ()
{
	int * ptr_item;
	int searchkey;

	printf ("Enter a searchkey: ");
	scanf ("%d", &searchkey);

	ptr_item = (int*) bsearch (&searchkey,
		my_array, 6, sizeof (int), compare_integers);

	if (ptr_item != NULL)
		printf ("%d is found in the array.\n",*ptr_item);
	else
		printf ("%d is not found in the array.\n",searchkey);
	return 0;
}