The bsearch() Function | C For Dummies Blog

Computer scientists, as well as various professionals wearing white lab coats, have determined that searching for data top-to-bottom is slow and clunky. Therefore, they devised a better, more logical way to search: The binary search.

The binary search algorithm finds data faster than just scanning for it by looking at every sequential tidbit in a buffer.

The key is to sort the data first. Then the search splits the sorted data based on the key value being searched.

For example, consider this array:

int v[] = { 23, 25, 1, 17, 20, 14, 3, 19 };

To search for the value 3, a program scans elements zero through n. Moving sequentially, after the seventh comparison the key value 3 is located. To search more efficiently, you first sort the values and then search “in the middle” for values less than, greater than, or equal to the key. By doing so, the process takes fewer steps, as illustrated in Figure 1.

Figure 1. A binary search.

After sorting, the middle value is compared with the key. In Figure 1, the value 3 is less than the middle. The top part of the array is ignored and the bottom half is split. Again, the comparison is made in the middle of the bottom half. This time, the key value 3 is found. The search takes only two steps.

While for a small data set the difference in search time may be insignificant, for huge data sets using a binary search is far more efficient than searching every single record.

Don’t fret over coding your own binary search function (though I think such a challenge would be fun) because the C library contains the bsearch() function, prototyped in the stdlib.h header file. Here is the man page format:

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

Argument key is the value to look for, sent as an address. The next three arguments describe the array or buffer: its location base; the number of elements or members, nmemb; and the size of each element, size. Finally comes a comparison function, which is conveniently identical to the compar() function used in the qsort() function. In fact, the final four arguments of bsearch() are the same as the arguments used in in qsort().

The function’s return value is the address of the matching array element, or NULL for no match.

Be aware that the bsearch() function works only on sorted data. The function doesn’t sort the data itself, but because its final four arguments are identical to those required by qsort(), this issue isn’t a problem. I use both functions in the following sample code, updated from last week’s Lesson:

2025_01_18-Lesson.c

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b)
{
    return( *(int *)a - *(int *)b );
}

int main()
{
    int v[] = { 23, 25, 1, 17, 20, 14, 3, 19 };
    int size,*r,key;

    /* obtain array size */
    size = sizeof(v)/sizeof(int);

    /* locate a value */
    printf("Input key value: ");
    scanf("%d",&key);

    /* sort the array */
    qsort( v, size, sizeof(int), compare);

    /* locate a value */
    r = bsearch( &key, v, size, sizeof(int), compare );
    if( r!=NULL )
        printf("Key %d found!\n",*r);
    else
        printf("Key %d not found.\n",key);

    return 0;
}

An input value is requested. Array v[] is sorted, then search by using the input value, key. Results are output, depending on whether key was found. Here’s a sample run:

Input key value: 17 Key 17 found!

Or:

Input key value: 88 Key 88 not found.

As I wrote in last week’s Lesson, the true measure of speed comes when search large data sets. Also, the bsearch() function searches more than integer arrays. In next week’s Lesson, I demonstrate using bsearch() to find strings.

2025_01_18-Lesson.c

Leave a Reply