Come è la funzione bsearch () nella libreria standard C implementato?

Question

Qualcuno sa come è implementato lo standard funzione di ricerca binaria?

Questo è il prototipo.

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

Sono davvero curioso di sapere come hanno usato puntatori void.

Answer 1

suppongo che voi siate interessati a sapere come puntatori void * vengono utilizzati nella bsearch, piuttosto che l'algoritmo di ricerca binaria vero e proprio. Il prototipo per bsearch è:

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

Qui, void * viene utilizzato in modo che qualsiasi tipo arbitrario può essere cercato. L'interpretazione dei puntatori è fatto dalla funzione compar (fornita dall'utente).

Dal momento che i punti di puntatore base per l'inizio di un array, e gli elementi di un array vengono garantiti per essere contigui, bsearch può ottenere un puntatore void * ad uno qualsiasi degli elementi nmemb nella matrice facendo l'aritmetica dei puntatori. Ad esempio, per ottenere un puntatore al quinto elemento dell'array (supponendo 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 */

Nel codice sopra, non potrebbe aggiungere size*n direttamente base perché è di tipo void * e aritmetica su void * non è definito.

Answer 2

bsearch @ Google codesearch per le diverse implementazioni di bsearch.

Answer 3

Guardate la fonte. Se si dispone di VS standard o meglio, vedi:

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