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.
#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
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.
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
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
qsortand 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 - arrayhas typeptrdiff_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:
bsearchcannot 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 inqsort.