自分用メモ

データ構造とアルゴリズムの勉強をしていたら、2分探索というものが出てきた。
超簡潔に述べると指定したデータを効率よく探す方法である。

※前提として、配列の中身は左から小さい順に並んでいるとする。
（例）[1, 4, 7, 9, 11, 15]

細かいことは置いといて、
探索する数値が配列の真ん中の値よりも、小さいのか、同じなのか、大きいのかで分類していく。探索する数値が真ん中の値と同じになれば、探索成功である。探索する数値が配列の真ん中よりも小さければ、真ん中の値を配列の最大の数として同じように、範囲を狭めていく。真ん中よりも大きい場合も同じようにしていく。
といった感じにやっていくと、最も手間がかかった際でも、

n (\frac{1}{2})^k  = 1 \\



n:全体の操作数の上限\\
k:nを半分にする操作の数

こう書けるので、操作数が

k=\log_2 n

となる。

参照URL：
http://www.grapecity.com/developer/support/powernews/column/clang/054/page03.htm

# include<stdio.h>

/*探索の対象の配列　――11個*/
int arry[] = {1, 3, 5, 8, 12, 16, 19, 24, 26, 31};

int main(void){
    /*配列の範囲を狭めるための添字*/
    int lowid, midid, highid;
    /*探索する値*/
    int target;

    /*添字の範囲を初期化*/
    highid = 10;
    lowid = 0;

    /*コマンドから入力*/
    scanf("%d", &target);

    /*値が見つかるまで繰り返す*/
    while (lowid <= highid){
        /*int型の計算なので小数点は切り捨て*/
        midid = (lowid + highid) / 2;
        /*過程を出力*/
        printf("lowid=%d, midid=%d. highid=%d¥n", lowid, midid, highid);

        /*見つかればループを抜ける*/
        if(arry[midid] == target){
            break;
        /*値の大小を調べて探索範囲を狭めていく*/
        }else if(arry[midid] < target){
            lowid = midid + 1;
        }else{
            highid = midid -1;
        }
    }
    /*探索の結果見つかれば値を表示*/
    if (arry[midid] == target){
        printf("値 %d は %d 番目に見つかりました。\n", target, midid + 1);
    }else{
        printf("値 %d は見つかりませんでした。", target);
    }
    return 0;
}