名称

bsearch − ソートされた表をバイナリ探索する

形式

#include <stdlib.h>

char ∗bsearch ((char ∗) key, (char ∗) base, nel, sizeof (∗key), compar)
unsigned nel;
int (∗compar)( );

解説

bsearch は、Knuth (6.2.1) アルゴリズム B を一般化したバイナリ探索ルーチンです。 表の中でデータが見つかったところを指すポインタを返します。 その表は、用意されている比較関数によって昇順に、 あらかじめソートされていなければなりません。 key は、表の中で検索されるデータの実体を指します。 base は表の先頭の要素を指します。 nel は表の要素の個数です。 compar は比較関数の名前です。 比較関数は、比較される要素を指す 2 つの引数を持つ関数です。 その関数は、第 1 引数が第 2 引数より大きい、等しい、小さいのいずれかに 従って、0 より大きい、等しい、小さい整数を返さなければなりません。

例

下の例は、 文字列とその長さを持つノードを指すポインタから成る表を検索します。 その表は、各エントリが指すノードの中の文字列に関して アルファベット順に並んでいます。

このコードの断片は、文字列を読み込み、 それに対応するノードを見つけ、その文字列とその長さを表示するか、 あるいはエラーメッセージを表示します。

#include <stdio.h>
#include <stdlib.h>
 #defineTABSIZE4
 struct node {/∗ これらは、table に格納される ∗/
char ∗string;
int length;
};
struct node table[TABSIZE] = {/∗ 検索される表 ∗/
{ "news", 4 },
{ "os", 2 },
{ "unix", 4 },
{ "workstation", 11 },
};
main()
{
struct node ∗node_ptr, node;
int node_compare( );  /∗ 2 つのノードを比較するルーチン ∗/
char str_space[20];   /∗ 文字列を読み込む場所 ∗/
 node.string = str_space;
while (scanf("%s", node.string) != EOF) {
node_ptr = (struct node ∗)bsearch((char ∗)(&node),
   (char ∗)table, TABSIZE,
   sizeof(struct node), node_compare);
if (node_ptr != NULL) {
(void)printf("string = %20s, length = %d\n",
node_ptr−>string, node_ptr−>length);
} else {
(void)printf("not found: %s\n", node.string);
}
}
}
/∗
このルーチンは、文字列フィールドがアルファベット順に
並んでいるものとして 2 つのノードを比較する。
∗/
int
node_compare(node1, node2)
struct node ∗node1, ∗node2;
{
return strcmp(node1−>string, node2−>string);
}

注意

キーと表の先頭の要素を指すポインタは、 その要素を指すポインタ型でなければならず、 その型へのキャストが必要です。
比較関数は、すべてのバイトを比較する必要はありません。 だから、比較される値に加えて任意のデータが 要素の中に含まれていてかまいません。 リターン値は、その要素を指すポインタ型にキャストされなけれるべきです。

関連事項

qsort(3)

診断

キーが表中に見つからなかったときは、 NULL ポインタが返されます。

NEWS-OSRelease 4.2.1R