Failure to work on string comparison using function pointer in C

Question

There are two versions of compare_first_character functions, and they are both passed into another function. However, the first would yield correct matches of words while the second would return nothing found despite there being one.

Version 1: [Version 1 of string comparison]

int compare_first_characters(const void *p, const void *q) {
    return **(char **)p - **(char **)q;
}

Version 2(fail): [Version 2 of string comparison]

int compare_first_characters(const void *p, const void *q) {
    return strcmp(*(char **)p, *(char **)q);
}

Suspected function where problems emerge:

    const void *found = bsearch(key, words, n, sizeof(words[0]), compare_first_characters);

Complete program:

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

int compare_first_characters(const void *p, const void *q) {
    return strcmp(*(char **)p, *(char **)q);
}

int main(int argc, char *argv[]) {
    char *words[] = {"red", "blue", "green", "yellow"};
    int n = sizeof(words) / sizeof(*words);
    const char *key = "g";

    qsort(words, n, sizeof(words[0]), compare_first_characters);
    printf("Sorted by first letter: \n");
    for (int i = 0; i < n; i++) {
        printf("%s ", words[i]);
    } 
    printf("\n");
    printf("Looking for a word that starts with '%s': ", key);
    const void *found = bsearch(key, words, n, sizeof(words[0]), compare_first_characters);
    printf("found '%s'\n", found ? *(const char **)found : "none");
    return 0;
}

Answer 1

The both your comparison functions called with bsearch are invalid.

The function bsearch is declared the following way

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

That is key must be passed by reference through a pointer to it.

However you are calling the function like

const void *found = bsearch(key, words, n, sizeof(words[0]), compare_first_characters);
                            ^^^  

So in the first comparison function this double dereferencing

int compare_first_characters(const void *p, const void *q) {
    return **(char **)p - **(char **)q;
}

of the pointer that corresponds to the argument key that actually has the type const char * according to its declaration

const char *key = "g";

invokes undefined behavior. You are wrong saying that using the first comparison function the program works correctly. Try for example to use another string as key as for example "y".

You have to write the function call like

const void *found = bsearch( &key, words, n, sizeof( words[0] ), compare_first_characters );
                             ^^^^

Pay attention to that the function strcmp compares whole strings. So to use the second comparison function you need to specify a string literal that is equal to one of the strings of the array In this case the both comparsion functions will work correctly.

And relative to the first comparison function then you should cast the void pointers to the unsigned character type const unsigned char **.

Here is your updated program.

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

int compare_first_characters1( const void *p, const void *q ) {
    return **( const unsigned char ** )p - **( const unsigned char ** )q;
}

int compare_first_characters2( const void *p, const void *q ) {
    return strcmp( *( char ** )p, *( char ** )q );
}

int main( void )
{
    const char *words[] = { "red", "blue", "green", "yellow" };
    int n = sizeof( words ) / sizeof( *words );
    const char *key1 = "y";

    qsort( words, n, sizeof( words[0] ), compare_first_characters1 );
    printf( "Sorted by first letter: \n" );
    for (int i = 0; i < n; i++)
    {
        printf( "%s ", words[i] );
    }
    printf( "\n" );
    printf( "Looking for a word that starts with '%s': ", key1 );
    const void *found = bsearch( &key1, words, n, sizeof( words[0] ), compare_first_characters1 );
    printf( "found '%s'\n", found ? *( const char ** )found : "none" );

    putchar( '\n' );

    const char *key2 = "yellow";
    qsort( words, n, sizeof( words[0] ), compare_first_characters2 );
    printf( "Sorted by first letter: \n" );
    for (int i = 0; i < n; i++)
    {
        printf( "%s ", words[i] );
    }
    printf( "\n" );

    printf( "Looking for a word that starts with '%s': ", key2 );
    found = bsearch( &key2, words, n, sizeof( words[0] ), compare_first_characters2 );
    printf( "found '%s'\n", found ? *( const char ** )found : "none" );
}

The program output is

Sorted by first letter:
blue green red yellow
Looking for a word that starts with 'y': found 'yellow'

Sorted by first letter:
blue green red yellow
Looking for a word that starts with 'yellow': found 'yellow'

By the way as all strings in the array differ by the first character then you can sort the array using the first comparison function and then search a target string as for example "yellow" or "green" using the second comparison function in the call of bsearch.

Here is updated previous program.

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

int compare_first_characters1( const void *p, const void *q ) {
    return **( const unsigned char ** )p - **( const unsigned char ** )q;
}

int compare_first_characters2( const void *p, const void *q ) {
    return strcmp( *( char ** )p, *( char ** )q );
}

int main( void )
{
    const char *words[] = { "red", "blue", "green", "yellow" };
    int n = sizeof( words ) / sizeof( *words );
    const char *key = "green";

    qsort( words, n, sizeof( words[0] ), compare_first_characters1 );
    printf( "Sorted by first letter: \n" );
    for (int i = 0; i < n; i++)
    {
        printf( "%s ", words[i] );
    }
    printf( "\n" );
    printf( "Looking for a word that starts with '%s': ", key );
    const void *found = bsearch( &key, words, n, sizeof( words[0] ), compare_first_characters1 );
    printf( "found '%s'\n", found ? *( const char ** )found : "none" );
}

Its output is

Sorted by first letter:
blue green red yellow
Looking for a word that starts with 'green': found 'green'

Answer 2

int compare_first_characters(const void *p, const void *q) {
    return strcmp(*(char **)p, *(char **)q);
}

1. it is total nonsense and invokes undefined behavior. *(char **)p is not an equivalent of (char *)p
2. strcmp compares whole strings not first characters.

if you want to compare strings

int compare_first_characters(const void *p, const void *q) {
    return !strcmp(p, q);
}

if only first characters

int compare_first_characters(const void *p, const void *q) {
    const char *a = p, *b = q;
    return *a == *b;
}

https://godbolt.org/z/MMEra35vY