bsearch() をちょっと改造してみた
bsearch() 関数のちょっと改造した版です。
bsearch() は、重複するキーが存在する場合、その中のいずれかひとつを返しますが、この関数は、最初のひとつを返します。
/*---------------------------------------------------------------------------*/ /* Performs binary search on a sorted array. */ /* Returns pointer to the first element that has the specified key; or NULL */ /* if the specified key was not found. */ /*---------------------------------------------------------------------------*/ const void *bsearch2(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *p, const void *q)) { size_t border_i; const void *border_p; int c; for (;;) { /* If the array has only a few element, search directly. */ if (nmemb == 0) return NULL; if (nmemb == 1) { return (compar(key, base) == 0) ? base : NULL; } if (nmemb == 2) { const void *fst = base; const void *snd = (const char *)base + size; if (compar(key, fst) == 0) return fst; if (compar(key, snd) == 0) return snd; return NULL; } /* Pick up a median element and compare it with the specified key. */ border_i = nmemb / 2; border_p = (const char *)base + size * border_i; c = compar(key, border_p); /* Search recursively... */ if (c > 0) { const void *new_base = (const char *)base + size * (border_i + 1); size_t new_nmemb = nmemb - (border_i + 1); /* return bsearch2(key, new_base, new_nmemb, size, compar); */ base = new_base; nmemb = new_nmemb; } else if (c < 0) { size_t new_nmemb = border_i; /* return bsearch2(key, base, new_nmemb, size, compar); */ nmemb = new_nmemb; } else { size_t new_nmemb = border_i + 1; /* return bsearch2(key, base, new_nmemb, size, compar); */ nmemb = new_nmemb; } } /* for (;;) */ }