How is the bsearch() function in the standard C library implemented?

Question

Does anyone know how the standard binary search function is implemented?

This is the prototype.

void * bsearch (const void*, const void*, size_t, size_t, int (*) (const void *, const void *) );

I'm really curious about how they used void pointers.

Answer 1

Look at the source. If you have VS Standard or better, see:

C:\Program Files\Microsoft Visual Studio 8\VC\crt\src\bsearch.c

Answer 2

See bsearch @ Google's codesearch for different implementations of bsearch.

Answer 3

I assume you are interested in knowing how void * pointers are used in bsearch, rather than the actual binary search algorithm itself. The prototype for bsearch is:

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

Here, void * is used so that any arbitrary type can be searched. The interpretation of the pointers is done by the (user-supplied) compar function.

Since the pointer base points to the beginning of an array, and an array's elements are guaranteed to be contiguous, bsearch can get a void * pointer to any of the nmemb elements in the array by doing pointer arithmetic. For example, to get a pointer to the fifth element in the array (assuming nmemb >= 5):

unsigned char *base_p = base;
size_t n = 5;
/* Go 5 elements after base */
unsigned char *curr = base_p + size*n;
/* curr now points to the 5th element of the array.
   Moreover, we can pass curr as the first or the second parameter
   to 'compar', because of implicit and legal conversion of curr to void *
   in the call */

In the above snippet, we couldn't add size*n directly to base because it is of type void *, and arithmetic on void * is not defined.