Невозможность работать при сравнении строк с использованием указателя функции в C

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

1. это полная ерунда и вызывает неопределенное поведение. *(char **)p не является эквивалентом (char *)p
2. strcmp сравнивает целые строки, а не первые символы.

если вы хотите сравнить строки

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

если только первые символы

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

https://godbolt.org/z/MMEra35vY

Обе ваши функции сравнения, вызванные с помощью bsearch, недействительны.

Функция bsearch объявляется следующим образом

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

То есть key нужно передавать по ссылке через указатель на него.

Однако вы вызываете функцию, например

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

Итак, в первой функции сравнения это двойное разыменование

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

указателя, соответствующего аргументу key, который фактически имеет тип const char * в соответствии с его объявлением

const char *key = "g";

вызывает неопределенное поведение. Вы ошибаетесь, говоря, что при использовании первой функции сравнения программа работает корректно. Попробуйте, например, использовать другую строку в качестве ключа, например, "y".

Вы должны написать вызов функции, например

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

Обратите внимание, что функция strcmp сравнивает строки целиком. Поэтому для использования второй функции сравнения необходимо указать строковый литерал, равный одной из строк массива. В этом случае обе функции сравнения будут работать корректно.

И относительно первой функции сравнения вы должны привести указатели void к беззнаковому типу символов const unsigned char **.

Вот ваша обновленная программа.

#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" );
}

Вывод программы

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'

Кстати, поскольку все строки в массиве отличаются по первому символу, то вы можете отсортировать массив с помощью первой функции сравнения, а затем искать целевую строку, например, "yellow" или "green", используя вторую функцию сравнения при вызове bsearch.

Здесь обновлена ​​предыдущая программа.

#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" );
}

Его вывод

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