bsearch - ライブラリコールの説明 - Linux コマンド集 一覧表

bsearch - ソートされた配列を二分木検索 (binary search) する

#include <stdlib.h>


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

bsearch () 関数は nmemb 個のオブジェクトからなる配列を検索 する。配列の最初のメンバーへのポインタは base によって与える。 ポインタ key で参照されるオブジェクトと一致するメンバーが返される。 配列中の各々のメンバーのサイズは size によって指定する。

配列の内容は比較関数 compar に基づき、昇順にソートされていなけれ ばならない。 compar ルーチンは二つの引数を取る関数で、一つ 目に key へのポインタ、次に配列のメンバーへのポインタを取る。 この順に指定したとき、 key が配列メンバーより小さいときには 負の整数を、大きいときには正の整数を、一致したときには 0 を、それぞれ compar は返さなければならない。

bsearch () 関数は、配列のメンバーのうち、一致したものへのポインタを 返す。見つからなかったときは NULL を返す。 key と一致したメンバーが 複数あるとき、そのうちのどのメンバーが返されるかはわからない。

以下の例は、   qsort (3) を使って構造体の配列の並び換えを行った後、 所望の要素を bsearch ()を使って取得するものである。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>



struct mi {
	int nr;
	char *name;
} months[] = {
	{ 1, "jan" }, { 2, "feb" }, { 3, "mar" }, { 4, "apr" },
	{ 5, "may" }, { 6, "jun" }, { 7, "jul" }, { 8, "aug" },
	{ 9, "sep" }, {10, "oct" }, {11, "nov" }, {12, "dec" }
};



#define nr_of_months (sizeof(months)/sizeof(months[0]))



static int compmi(const void *m1, const void *m2) {
	struct mi *mi1 = (struct mi *) m1;
	struct mi *mi2 = (struct mi *) m2;
	return strcmp(mi1->name, mi2->name);
}



int main(int argc, char **argv) {
	int i;



	qsort(months, nr_of_months, sizeof(struct mi), compmi);
	for (i = 1; i < argc; i++) {
		struct mi key, *res;
		key.name = argv[i];
		res = bsearch(&key, months, nr_of_months,
			      sizeof(struct mi), compmi);
		if (res == NULL)
			printf("'%s': unknown month\n", argv[i]);
		else
			printf("%s: month #%d\n", res->name, res->nr);
	}
	return 0;
}

SVr4, 4.3BSD, POSIX.1-2001, C99

  hsearch (3),   lsearch (3),   qsort (3),   tsearch (3)