Is there a Binary Search method in the C standard library?

Question

I cannot find any method implementing binary search. Is that because I failed to locate it, or is it because it doesn't exist?

_{I think the second, but I couldn't find a duplicate question, so maybe I am wrong.}

Answer 1

There is the bsearch() method in the same <stdlib.h>, as is listed here, here and here.

Note: C standard does not guarantee that the function implements binary search.

The bsearch() function uses the search algorithm to find an element that matches key in a sorted array of n elements of size size. (The type size_t is defined in <stdlib.h> as unsigned int.) The last argument, compare, gives bsearch() a pointer to a function that it calls to compare the search key with any array element. This function must return a value that indicates whether its first argument, the search key, is less than, equal to, or greater than its second argument, an array element to test..

You should generally use qsort() before bsearch(), because the array should be sorted (should be in ascending order, ordered with the same criteria used by compare) before searching. This step is necessary because the binary search algorithm tests whether the search key is higher or lower than the middle element in the array, then eliminates half of the array, tests the middle of the result, eliminates half again, and so forth. If you define the comparison function for bsearch() with identical types for its two arguments, then qsort() can use the same comparison function.

The bsearch() function returns a pointer to an array element found that matches the search key. If no matching element is found, bsearch() returns a null pointer.^[a]

Example Use:

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

Output:

40 is in the array.

In response to a comment below as to how to find the first element that is less/greater than key, here is a (probably dirty) workaround: you can iterate over the sorted array and compare its elements to key using the same compare function passed to this method, until you find an element less/greater than key.