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 (;;) */
}