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

#define N 100000

int linear_search(int data[], int n, int query) {
    int i;
    for (i=0; i<n; i++) {
        if (query == data[i]) {
            return i;
        }
    }
    return -1;
}

int binary_search(int data[], int n, int query) {
    int left = 0;                // 探す範囲の左端
    int right = n;         // 探す範囲の右端(defineしてある)
    int middle = (right+left)/2; // 真中
    while (right-left >= 0) {
        if (query < data[middle]) { // もし真中の値のほうが大きかったら
            right = middle-1;        // 右端を middle の一個左に設定
        } else if (query > data[middle]) {//もし真中の値のほうが小さかったら
            left = middle+1;         // 左端を middle の一個右に設定
        } else {
            // 発見!
            return middle;
        }
        middle = (right+left)/2;        //真中を再計算
    }
    return -1;
}

int main()
{
    int data[N]; /* 対象データ */
    int query[N]; /* data の中で探す数値の配列 */
    int i;
    int id;
    long start, end;
    double time_used;

    for (i=0; i<N; i++) {
        data[i] = i;
        query[i] = i;
    }
    
    /* 逐次探索をN回行って経過時間を測定 */
    start = clock();
    for (i=0; i<N; i++) {
        id = linear_search(data, N, query[i]);
    }
    end = clock();
    time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("逐次探索の処理時間: %fs\n", time_used);

    /* 二分探索をN回行って経過時間を測定 */
    start = clock();
    for (i=0; i<N; i++) {
        id = binary_search(data, N, query[i]);
    }
    end = clock();
    time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("二分探索の処理時間: %fs\n", time_used);
}