bsearch

2章の最後は、NetBSDのCライブラリのbsearch関数。
整列してある配列（開始base0、長さnmemb）からkeyの位置を検索する関数。

void *
bsearch(key, base0, nmemb, size, compar)
    register const void *key;
    const void *base0;
    size_t nmemb;
    register size_t size;
    register int (*compar) __P((const void *, const void *));
{
    register const char *base = base0;
    register int lim, cmp;
    register const void *p;

    for (lim = nmemb; lim != 0; lim >>= 1) {
        p = base + (lim >> 1) * size;
        cmp = (*compar)(key, p);
        if (cmp == 0)
            return ((void*) p);
        if (cmp > 0) {
            base = (char *) p + size;
            lim--;
        }
    }
    return (NULL);
}

このコードはvariant、invariantの説明で使っています。
いままでのなかでは一番短い（ライブラリ関数だし）。
演算lim >> 1は1/2にする処理。