STEP 2.4 整列化されているデータの探索/検索
線形探索 (リニアサーチ)

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;
}