N個のデータから、特定のキーに対応するデータを探す(検索する)ことを考えよう。
準備で作成した100万未満のデータが10万個、昇順に整列化されている10万行のファイル data.txtを配列に読み込む。
そのデータに、入力される整数のキーを値にする配列があれば、そのインデックスを示せ。なければ-1を出力せよ。
<問題>
配列の頭からはじめて、順にキーを探索していくだけの素朴な探索/検索方法を、線形探索と呼ぶ(リニアサーチとか、シーケンシャルサーチともよぶ)。
線形探索をプログラムせよ。(データが整列化されているので、STEP2.1 の変形。番兵は使わなくてもよい)
実行例
key ? : 99732
data[9999] = 99732
key ? : 999998
data[99999] = 999998 (一番最後のデータに発見 !)
key? : 78 (私のデータでは、data[11] = 71, data[12] = 79。STEP2.1 と違い、このデータは整列化されているので、ここで、もうこのkeyはない、とわかるはず)
-1
<ヒント>
解答例 #include <stdio.h> #include <stdlib.h> #define DATA_SIZE 100000 int main(void) { long data[DATA_SIZE]; long i = 0; FILE *fp; char buffer[16]; long key; printf ("Key? : "); scanf ("%ld", &key); fp = fopen("data.txt", "r"); while (fgets(buffer, sizeof (buffer), fp) != NULL) { sscanf(buffer, "%ld", &data[i]); i++; } fclose (fp); for (i = 0; i < DATA_SIZE; i++) { if (data[i] == key) { printf ("data[%ld] = %ld\n", i, key); break; } else if (data[i] > key) { printf("-1\n"); break; } } if (i == DATA_SIZE) /* 最後までない */ printf("-1\n"); return 0; }