【C言語】二分探索（バイナリサーチ）の仕組みと実装方法をわかりやすく解説

二分探索（バイナリサーチ）は、ソート済み（整列済み）のリストにのみ適用できる高速な探索アルゴリズムです。対象となるリストを半分ずつに分割しながら、探索したいキー（目的の値）と中央の要素を繰り返し比較することで、少ない手順で目的の値を見つけ出します。

二分探索の基本的な仕組み

二分探索では、キーと中央の要素を比較した結果として、次の3つのケースが考えられます。

• 中央の要素がキーと一致する場合 … 探索は成功し、そこで終了します。
• 中央の要素がキーより大きい場合 … 探索範囲を左側（より小さい値側）の領域に絞って続行します。
• 中央の要素がキーより小さい場合 … 探索範囲を右側（より大きい値側）の領域に絞って続行します。

この「範囲を半分に絞る」操作を繰り返すことで、線形探索のように先頭から順番に調べる必要がなくなり、大幅に探索回数を削減できます。

入力と出力

入力（Input）

• ソート済みの要素リスト
• 探索するキー（目的の値）

出力（Output）

• 成功 … キーが見つかった場合
• 失敗 … キーが存在しない場合

C言語による二分探索の実装例

以下は、二分探索を実装したC言語のサンプルプログラムです。変数 low と high で探索範囲の両端を管理し、mid が中央位置を表します。

#include<stdio.h>
int main(){
    int a[50], n, i, key, flag = 0, low, mid, high;
    printf("enter the no: of elements:");
    scanf("%d",&n);
    printf("enter the elements:");
    for(i=0; i<n; i++)
        scanf("%d", &a[i]);
    printf("enter a key element:");
    scanf("%d", &key);
    low = 0;
    high = n-1;
    while (low<=high){
        mid = (low + high) / 2;
        if (a[mid] == key){
            flag = 1;
            break;
        } else {
            if (a[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    if (flag == 1)
        printf("search is successful");
    else
        printf("search is unsuccessful");
    return 0;
}

プログラムのポイント

• low = 0、high = n-1 で探索範囲の初期化を行います。
• mid = (low + high) / 2 で中央位置を計算し、a[mid] をキーと比較します。
• キーが見つかればフラグ flag を立ててループを抜け、見つからなければ探索範囲を更新して処理を続けます。
• low > high になると探索範囲が空になったことを意味するため、ループが終了し「探索失敗」と判定されます。

実行結果

上記のプログラムを実行すると、以下のような結果が出力されます。

enter the no: of elements:5
enter the elements:23
45
57
89
90
enter a key element:45
search is successful

この例では、ソート済みの配列 {23, 45, 57, 89, 90} からキー「45」を探索しています。最初の中央要素は「57」ですが、45の方が小さいため左側の領域に絞られ、次の比較で「45」が見つかり、探索成功となっています。

二分探索の計算量

二分探索は、1回の比較ごとに探索範囲が半分になるため、時間計算量は O(log n) です。これは先頭から順に調べる線形探索の O(n) と比べて非常に高速で、データ件数が多いほど効果を発揮します。ただし、事前にデータがソートされていることが前提条件である点には注意しましょう。