C言語のきほん「２分探索」

実際のプログラムでは、たくさんのデータの中から目的のデータを見つけ出す処理が行われる。

以前、本ブログでは、「線形探索」をご紹介している。

今回は、「２分探索」をご紹介する。これは、範囲を半分に絞りながら目的となる値を見つける方法である。

では、「２分探索」を使う例をプログラムでみてみよう。

なお、本プログラムは、Windows 11 Home（23H2）上で、
Visual Studio Code（1.91.1）を使用して作成し、gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0でコンパイルしている。

//2分探索

#include <stdio.h>

#define DATA_NUM 10;
int data[] = {2,8,11,12,34,58,64,73,88,99};

int main(void)
{
    //見つけたい値
    int target = 58;
    int left_index = 0;
    int right_index = DATA_NUM -1;
    int middle_index = 0;

    while(left_index <= right_index) {
        middle_index = (left_index + right_index)/2;

        //確認用
        printf("left:%d,middle:%d,right:%d\n",left_index,middle_index,right_index);

        if (data[middle_index] == target) {
            printf("値%dは、data[%d]に見つかりました\n",target,middle_index);
            return 0;
        } else if (data[middle_index] < target) {
            left_index = middle_index +1;
        } else {
            right_index = middle_index -1;
        }
    }
    printf("値%dは見つかりませんでした\n",target);
    return 0;
}

実行結果

left:0,middle:5,right:10
値58は、data[5]に見つかりました

配列dataの中から変数targetの値を２分探索で探している。
範囲の左端を「left_index」、右端を「right_index」で表す。

whileループの中では、調べる範囲の中央を「middle_index」として、この場所の値（data[middle_index])をtargetの値と比較する。
「middle_index」の値は、左端と右端のインデックスを足して２で割ることで求めている。
int型同士の割り算をしているので、小数点以下は切り捨てられる。
この値が等しければ、処理を終了する。
そうでなければ、data[middle_index]の値がtargetの値より小さい場合は、左端のインデックスをmiddle_index+1に設定して次のループに進む。
data[middle_index]の値がtargetの値より大きい場合は、右端のインデックスをmiddle_index-1に設定して次のループに進む。

もし、ループが終わってしまったら、値が見つからなかったということになる。

（参考）「C言語新版ゼロからはじめるプログラミング」三谷純（著）翔泳社