bsearch


function
<cstdlib> 
void * bsearch ( const void * key, const void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

Binary search in array

Searches the given key in the array pointed by base that is formed by num elements, each of a size of size bytes, and returns a void* pointer to the first entry in the table that matches the search key.

To perform the search, the function compares the elements to the key by calling the function comparator specified as the last argument.

Because this function performs a binary search, the values in the base array are expected to be already sorted in ascending order, with the same criteria used by comparator.

Parameters

key
Pointer to the object that serves as key for the search, type-casted as a void*.
base
Pointer to the first object of the array where the search is performed, type-casted as a void*.
num
Number of elements in the array pointed by base.
size
Size in bytes of each element in the array.
comparator
Function that compares two elements. The function shall follow this prototype:

int comparator ( const void * elem1, const void * elem2 );

The function must accept two parameters that are pointers to elements, type-casted as void*. These parameters should be cast back to some data type and be compared.

The return value of this function should represent whether elem1 is considered less than, equal, or grater than elem2 by returning, respectively, a negative value, zero or a positive value.

For types that support regular comparison operators, a general comparator function may look like:

1
2
3
4
5
6
 
int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a <  *(MyType*)b ) return -1;
}




Return Value

A pointer to an entry in the array that matches the search key.
If key is not found, a NULL pointer is returned.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
/* bsearch example */
#include <stdio.h>
#include <stdlib.h>

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

int values[] = { 10, 20, 25, 40, 90, 100 };

int main ()
{
  int * pItem;
  int key = 40;
  pItem = (int*) bsearch (&key, values, 6, sizeof (int), compareints);
  if (pItem!=NULL)
    printf ("%d is in the array.\n",*pItem);
  else
    printf ("%d is not in the array.\n",key);
  return 0;
}


In the example there is an array of sorted int values. There is also a function called compare that compares the values pointed by the two parameters as if they were pointers to int values (which they indeed are) and returns the result of the subtraction of the values pointed by both, which gives 0 as result if they are equal, a positive result if the value pointed by a is greater than the pointed by b or a negative result if the value pointed by b is greater.

In the main, function there is a call to bsearch with 40 as key, so the function finds that key in the array of values and the program prints out:


40 is in the array.


For C strings, strcmp can directly be used as the last argument for bsearch:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
/* bsearch example with strings */
#include <stdio.h>
#include <stdlib.h>

char strvalues[][20] = {"some","example","strings","here"};

int main ()
{
  char * pItem;
  char key[20] = "example";

  /* sort elements in array: */
  qsort (strvalues, 4, 20, (int(*)(const void*,const void*)) strcmp);

  /* search for the key: */
  pItem = (char*) bsearch (key, strvalues, 4, 20, (int(*)(const void*,const void*)) strcmp);

  if (pItem!=NULL)
    printf ("%s is in the array.\n",pItem);
  else
    printf ("%s is not in the array.\n",key);
  return 0;
}


See also

qsort Sort elements of array (function)