SIMPLE SOLUTIONS

BSEARCH(3) - Linux manual

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

2003-11-01
BSEARCH(3) Linux Programmer's Manual BSEARCH(3)

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 と一致したメンバーが 複数あるとき、そのうちのどのメンバーが返されるかはわからない。

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

以下の例は、 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); } exit(EXIT_SUCCESS); }

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

この man ページは Linux man-pages プロジェクトのリリース 3.79 の一部 である。プロジェクトの説明とバグ報告に関する情報は http://www.kernel.org/doc/man-pages/ に書かれている。
2003-11-01 BSEARCH(3)
bsearch(3).txt (日本語 / Japanese)
Index English version of bsearch(3)
Go top