準備で作成した100万未満のデータが10万個、昇順に整列化されている10万行のファイル data.txtを配列に読み込む。
そのデータに、入力される整数のキーを値にする配列があれば、そのインデックスを示せ。なければ-1を出力せよ

整数が昇順に整列された大きさN(10万)の配列A (data)に整数X (key)があるかを判定する。ある場合は、インデックスを示す。なければ-1を出力する。

入力：配列Aと整数X
出力：配列Aに整数Xがある場合は、インデックスを出力。ない場合は-1

実行例

基本的な部分

1. low = 0, high = N-1, mid = (low+high)/2 とする。.5は切り捨てる。　（初期化）
2. low > high なら、終了条件2
3. S[mid] == Key なら、終了条件１
4. そうでないとき、Key < S[mid] ならhigh=mid-1、A[mid] < Key ならlow = mid+1　として、2へ

二分探索をプログラムせよ。（STEP2.4の探索部分を、取り替えなさい）

解答例

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000

int main(void) {
    long data[DATA_SIZE];
    long i = 0;
    FILE *fp;
    char buffer[16];
    long key;

    long a,b,c;

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

/* 以下、二分探索 */

    a = 0;
    b = DATA_SIZE -1;

/* 以下、解答 */
    while (a <= b) { /* 終了条件2でない間 */
        c = (a + b) /2; /* 整数の割り算なので、切り捨て */
        if (data[c] == key) { /* 終了条件1 */
            printf ("data[%ld] = %ld\n", c, key);
            break;
        } else if (data[c] > key) /* cより前にある */
            b = c - 1;
        else if (data[c] < key) /* cより後ろにある */
            a = c + 1 ;

    }

    if (a > b) /* ループを抜けてきた状態を確認する方法。教科書には、見つけたかどうか、flagを使う方法も、多くみられる */
        printf("-1\n");

    return 0;

}

STEP 2.5 (二分探索）