Как реализована функция bsearch() в стандартной библиотеке C?

Question

Кто-нибудь знает, как реализована стандартная функция двоичного поиска?

Это прототип.

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

Мне действительно интересно, как они использовали указатели void.

Answer 1

Полагаю, вам интересно узнать, как void * указатели используются в bsearch, а не сам алгоритм двоичного поиска.Прототип для bsearch является:

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

Здесь, void * используется для поиска любого произвольного типа.Интерпретация указателей выполняется (предоставляется пользователем) compar функция.

Поскольку указатель base указывает на начало массива, и элементы массива гарантированно будут смежными, bsearch может получить void * указатель на любой из nmemb элементы массива, выполняя арифметику указателей.Например, чтобы получить указатель на пятый элемент массива (при условии, что 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 */

В приведенном выше фрагменте мы не смогли добавить size*n прямо к base потому что это типа void *, и арифметика на void * не определен.

Answer 2

Видеть bsearch @ кодовый поиск Google для различных реализаций bsearch.

Answer 3

Посмотрите источник.Если у вас VS Standard или выше, см.:

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