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.

The bsearch() function uses the binary 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.

Answer 2

The C library has a standard function bsearch, declared in <stdlib.h>, for exactly this purpose: locate a matching entry in a table of entries sorted in ascending order according to a given comparison function.

Here is the specification in the C Standard:

7.22.5.1 The bsearch function

Synopsis

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

Description

The bsearch function searches an array of nmemb objects, the initial element of which is pointed to by base, for an element that matches the object pointed to by key. The size of each element of the array is specified by size.

The comparison function pointed to by compar is called with two arguments that point to the key object and to an array element, in that order. The function shall return an integer less than, equal to, or greater than zero if the key object is considered, respectively, to be less than, to match, or to be greater than the array element. The array shall consist of: all the elements that compare less than, all the elements that compare equal to, and all the elements that compare greater than the key object, in that order.³⁰⁸⁾

Returns

The bsearch function returns a pointer to a matching element of the array, or a null pointer if no match is found. If two elements compare as equal, which element is matched is unspecified.

---

_{308) In practice, the entire array is sorted according to the comparison function.}

This function has 2 shortcomings:

• if the table contains duplicate matching entries, it is unspecified which entry will be returned, as emphasised in the last paragraph above.
• the function cannot be used to locate the position where to insert the entry if it is not found in the table, it just returns a null pointer.

Here is a simple implementation that fixes the first point (it is coded to always return the matching entry closest to the beginning of the array) and can be modified to address the second:

#include <stdlib.h>

void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))
{
    const unsigned char *p;
    size_t m;
    int r;

    while (nmemb > 0) {
        m = (nmemb - 1) >> 1;
        p = (const unsigned char *)base + m * size;
        if ((r = compar(key, p)) < 0) {
            nmemb = m;
        } else
        if (r > 0) {
            base = p + size;
            nmemb -= m + 1;
        } else
        if (m == 0) {
            return (void *)p;
        } else {
            /* continue search to return first matching entry */
            nmemb = m + 1;
        }
    }
    // if you want the insertion point, you can return p here
    return NULL;
}