When learning the bsearch() function, it helps to start with integers, as demonstrated in last week’s Lesson. When the data is more complex, however, additional programming kung-fu is required to sort and search. The first hill to climb in this adventure is to hunt down a string.

Before setting out, remember that to find one string inside another you use the strstr() function. For finding a single string in an array of strings, the bsearch() function works well.

The issue with an array of strings is that it’s a cleverly disguised array of pointers:

char *fruit[] = {
    "cantalope", "grapefruit", "fig", "melon",
    "banana", "apple", "kiwi", "lemon"
};

The fruit[] array holds the addresses of the strings it references. These addresses are character pointers. This data type is what’s referenced in the qsort() function, which sorts the array, as well as the bsearch() function, which searches for a matching string in the array.

Here’s the qsort() function’s format:

qsort( fruit, size, sizeof(char *), compare);

The array and its size value come first (size is the number of elements). The next argument is the size of each element, which is not a string length. No, it’s the size of a character pointer, char *. Finally comes the compare() function’s name.

Here are the arguments for the bsearch() function:

bsearch( &key, fruit, size, sizeof(char *), compare );

The address of string key is what the bsearch() function searches for. The rest of the arguments are the same as for the qsort() function.

Both functions can share the same compare() function. For this operation the strcmp() function compares strings. But remember that the compare() function is sent two void pointers. These must be typecast to strings and properly addressed as pointer-pointers for the comparison to work:

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

The (const char **) typecast identifies each variable as a pointer-pointer, or the address of a string. (I find “address of a string” to be a better way to describe the pointer-pointer thing.) This value is an address, which is why the cast is prefixed with the * to dereference the address and represent the string itself. These two values are compared in the strcmp() function, with the result returned. This operation applies to both the qsort() and bsearch() functions to sort and search the array of strings.

Here is sample code:

2025_01_25-Lesson.c

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

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

int main()
{
    char *fruit[] = {
        "cantalope", "grapefruit", "fig", "melon",
        "banana", "apple", "kiwi", "lemon"
    };
    char *key;    /* input buffer must be allocated */
    char **r;
    int size;

    /* obtain array size */
    size = sizeof(fruit)/sizeof(char *);

    /* locate a value */
    key = malloc(32);
    if (key==NULL) exit(1);
    printf("Fruit: ");
    scanf("%s",key);

    /* sort the array */
    qsort( fruit, size, sizeof(char *), compare);

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

    return 0;
}

The program’s output:

Fruit: banana
Key banana found!

Just as with sorting complex data, the tricky part is to properly code the compare() function. For next week’s Lesson, I apply this insanity to sorting and searching an array of structures.