サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ヒープ領域＞バイナリサ−チ
[ヒープというデータ構造]←このソース→[分割コンパイル]
/* 今日はバイナリサーチ（２分検索）について学びます。ある配列があったとします。この配列は予め昇順にソートされているとします。例えば、下記の配列を見て下さい。
const char *base[ ] = { "atto ", "centi", "deca ", "deci ",
"exa ", "femto", "giga ", "hecto",
"kilo ", "mega ", "micro", "milli",
"nano ", "peta ", "pico ", "tera "
};
これは、文字列の配列です。（文字列の意味については、国際単位系の接頭辞を参照して下さい。）この中から、"deca "を効率良く探すには、どうすれば良いでしょうか。その方法のひとつとして、バイナリサーチがあります。バイナリサーチでは、以下の手順でキー（検索対象のデータ）を探します。
配列の中央の要素とキーを比較。
もし等しければ、それが検索対象のデータなので、呼び出し元へ戻る。
もしキーの方が大きければ、キーは中央の要素より右にあるので、中央の要素＋１から右を探す。
もしキーの方が小さければ、キーは中央の要素より左にあるので、左端の要素から、中央の要素−１までを探す。
以上の手順を繰り返すことにより、検索対象の配列の要素が減少していきます。ひとつのステップで半分になり、効率良く検索ができます。
この様にデーターを分割しながら探索などの処理をすることを、分割統治法といいます。 */
#include <stdio.h>
#include <string.h> /* strcmp( ), size_t で必要 */
#define NUM_DATA 16
const char *base[NUM_DATA] = {"atto", "centi", "deca ", "deci ",
"exa ", "femto", "giga ", "hecto",
"kilo ", "mega ", "micro", "milli",
"nano ", "peta ", "pico ", "tera "
};
/* バイナリサーチを行う */
int BSearch(const char *key, const char *base[ ], int bottom, int top);
void main(void);
int BSearch(const char *key, const char *base[ ], int bottom, int top)
{
int middle;
int temp;
if (bottom == top) /* 探索範囲が０になったら */
return (-1); /* 戻り値を訂正。Ｏさんご指摘ありがとうございました。 */
middle = (top + bottom) / 2; /* 中央の要素を求める */
/* 一致したらリターンする */
if ((temp = strcmp(key, base[middle])) == 0)
return (middle);
else if (temp > 0) /* 中央の要素より右を探す */
/* Ｏさんのご指摘により、訂正 */
if(top == middle + 1)
BSearch(key, base, middle, top + 1);
else
BSearch(key, base, middle + 1, top);
/* 訂正終り */
else /* 中央の要素より左を探す */
BSearch(key, base, bottom, middle);
}
void main(void)
{
int i;
int temp;
const char *key = "tera "; /* 検索対象の文字列 */
int top = NUM_DATA - 1;
int bottom = 0;
printf("キーワード：%s\n", key);
printf("検索対象のデータ：\n", key);
for (i = 0; i < NUM_DATA; i++)
printf("\t%s\n", base[i]);
if ((temp = BSearch(key, base, bottom, top)) != -1)
printf("\n見つかりました: %s は %d 番目の要素です。\n",
base[temp], temp + 1);
else
printf("\n見つかりません。\n");
}
|
[ヒープというデータ構造]←このソース→[分割コンパイル]
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−