bsearch()
bsearch()
この関数の目的
bsearch()は、配列の要素を二分法で検索する。定義
#include <stdlib.h> void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
働き
この関数は base が最初の要素を指している、 nmemb 個の要素をもつ配列を検索し、 key が指すオブジェクトに適合するものを見つける。個々の配列の要素のサイズは size によって指定される。
compar が指す比較関数の引数には key と配列の要素がこの順番で渡される。関数は key の方が配列の要素より小さいか、等しいか、大きいかによって負、ゼロ、正の値を返さなければならない。配列の要素は、 key より小さいもの、等しいもの、より大きいものの順番に並んでいなければならない。（実際には、すべての要素は比較関数にしたがってソートされているものである。）
返り値は、適合するものがあれば、適合する配列の要素であり、そうでなければヌルポインタである。二つ以上の要素が適合した場合にどれへのポインタが返されるは未指定である。
解説
仕様の中には二分法を使って検索するとはどこにも書いていないが、関数名の bsearch はほぼ間違いなく binary search のことであり、実装が二分法である処理系が殆どであろう。
検索する配列をソートするには、同じ比較関数を使って qsort() を呼ぶのが簡単である。
void* には何でも渡せる半面、型チェックが働かないので気をつけよう。
二分法とは何か？これは規則によって順番にソートされた配列から特定の要素を検索するアルゴリズムの一つで、配列のサイズが大きいときに特に有効である。詳しくはアルゴリズムの本に書いてある。
たとえば、文字列へのポインタの配列からある文字列を検索したいとしよう。この場合では strcmp() が比較関数として使える。
