C++

Reference

<cstdlib> (stdlib.h)

function
<cstdlib>

bsearch

void* bsearch (const void* key, const void* base,               size_t num, size_t size,               int (*compar)(const void*,const void*));
Binary search in array
Searches the given key in the array pointed to by base (which is formed by num elements, each of size bytes), and returns a void* pointer to a matching element, if found.

To perform the search, the function performs a series of calls to compar with key as first argument and elements of the array pointed to by base as second argument.

Because this function may be optimized to use a non-linear search algorithm (presumably a binary search), the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater. This requirement is fulfilled by any array ordered with the same criteria used by compar (as if sorted with qsort).

Parameters

key
Pointer to the object that serves as key for the search, type-casted to a void*.
base
Pointer to the first object of the array where the search is performed, type-casted to a void*.
num
Number of elements in the array pointed to by base.
size_t is an unsigned integral type.
size
Size in bytes of each element in the array.
size_t is an unsigned integral type.
compar
Pointer to a function that compares two elements.
This function is called repeatedly by bsearch to compare key against individual elements in base. It shall follow the following prototype:
1
 
int compar (const void* pkey, const void* pelem);
Taking two pointers as arguments: the first is always key, and the second points to an element of the array (both type-casted to const void*). The function shall return (in a stable and transitive manner):
return valuemeaning
<0The element pointed to by pkey goes before the element pointed to by pelem
0The element pointed to by pkey is equivalent to the element pointed to by pelem
>0The element pointed to by pkey goes after the element pointed to by pelem

For types that can be compared using regular relational operators, a general compar 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 there are more than one matching elements (i.e., elements for which compar would return 0), this may point to any of them (not necessarily the first one).
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
23
 
/* bsearch example */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */

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

int values[] = { 50, 20, 60, 40, 10, 30 };

int main ()
{
  int * pItem;
  int key = 40;
  qsort (values, 6, sizeof (int), compareints);
  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, compareints compares the values pointed to by the two parameters as int values and returns the result of subtracting their pointed values, which gives 0 as result if they are equal, a positive result if the value pointed to by a is greater than the one pointed to by b or a negative result if the value pointed to by b is greater.

In the main function the target array is sorted with qsort before calling bsearch to search for a value.

Output:
40 is in the array.


For C strings, strcmp can directly be used as the compar 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
24
 
/* bsearch example with strings */
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort, bsearch, NULL */
#include <string.h>     /* strcmp */

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

Output:
example is in the array.


Complexity

Unspecified, but binary searches are generally logarithmic in num, on average, calling compar approximately log2(num)+2 times.

Data races

The function accesses the object pointed to by key and any number of the num elements in the array pointed to by base, but does not modify any of them.

Exceptions (C++)

If comp does not throw exceptions, this function throws no exceptions (no-throw guarantee).

If key does not point to an object size bytes long, or if base does not point to an array of at least num properly arranged elements of size bytes each, or if comp does not behave as described above, it causes undefined behavior.

See also

qsort
Sort elements of array (function)