Skip to content
Tutorials Center
My learning

Topics

C Reference ยท stdlib.h

C bsearch() function

Reference for C bsearch(): find an element in a sorted array in O(log n) with a comparison callback, compute the index, and avoid the common mistakes.

bsearch() looks for a key in an array that is already sorted. It repeatedly halves the search range, so it needs only about log2(n) comparisons. Like qsort() it works on any element type through a comparison callback.

It returns a pointer to a matching element or NULL. It does not return an index; subtract the array start to get one.

C
#include <stdlib.h>

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

Try it

C Finding values and indexes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

C Searching structs by one field

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Syntax

C
void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));
Name Description
key Pointer to the value you are looking for.
base Pointer to the first element of the sorted array.
nmemb Number of elements.
size Size of one element in bytes.
compar Called as compar(key, element). Returns negative if the key sorts before the element, zero if equal, positive if after.

Returns: a pointer to a matching element, or NULL if there is none. The return type is void * even though the array is const; do not modify a const array through it.

Errors / undefined behavior: if the array is not sorted consistently with the comparator, the result is unspecified. A null base with nmemb > 0 is undefined behavior.

Usage notes

  • The array must be sorted with the same ordering the comparator uses. Sorting with qsort and one comparator, then searching with a different one, silently gives wrong answers.
  • The key is always the first argument of the comparator, and the second argument is an array element. That asymmetry lets the key have a different type from the elements, as in the second example.
  • Duplicates: if several elements are equal to the key, any one of them may be returned, not necessarily the first. To find the first or last of a run, write your own binary search or walk outwards from the hit.
  • Index calculation: hit - array has type ptrdiff_t, printed with %td.
  • Complexity: O(log n) comparisons. Searching an unsorted array needs a linear scan; sorting first only pays off when you search many times.
  • Insertion position: bsearch cannot tell you where a missing key would go. For that, write a lower-bound loop.
  • Pointer arrays: when sorting an array of strings the comparator must dereference char **, just as in qsort.