Как реализована функция bsearch() в стандартной библиотеке C?
Кто-нибудь знает, как реализована стандартная функция двоичного поиска?
Это прототип.
void * bsearch (const void*, const void*, size_t, size_t, int (*) (const void *, const void *) );
Мне действительно любопытно, как они использовали пустые указатели.
3 ответа
Я полагаю, вам интересно знать, как 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 * не определено.
Смотрите bsearch @ Google codesearch для различных реализаций bsearch,
Посмотрите на источник. Если у вас VS Standard или лучше, смотрите:
C: \ Program Files \ Microsoft Visual Studio 8 \ VC \ crt \ src \ bsearch.c