C言語で学ぶ二分探索の実装方法（反復版・再帰版の完全解説）

二分探索（バイナリサーチ）は、「比較」と「分割」の仕組みに基づく効率的な検索アルゴリズムです。半区間探索」「対数探索」「バイナリチョップなどの別名でも知られています。このアルゴリズムは、ソート済みの配列の中から目的の値（ターゲット）の位置を探し出します。

具体的な流れは以下のとおりです。まずターゲット値を配列の中央の要素と比較します。中央の要素がターゲットと一致すれば、そのインデックスを返して終了です。一致しない場合は、比較結果に応じて検索範囲を半分に絞ります。ターゲットが中央の値より小さければ前半部分を、大きければ後半部分を対象とし、見つかるまで同じ手順を繰り返します。

入力:
A[] = {0,2,6,11,12,18,34,45,55,99}
n=55

出力:
55 at Index = 8

動作の解説

上記の配列を例に、実際の探索の流れを見てみましょう。

まず、検索値 55 を配列の中央の要素である 18 と比較します。18 は 55 より小さいため、検索範囲を後半部分の配列 {34, 45, 55, 99} に絞り込みます。次に、この部分配列の中央である 55 と照合すると一致したため、インデックス 8 を返します。

もし検索値が中央の値より小さかった場合は前半部分を対象とし、要素が中央に現れるまで同じ操作を繰り返すことになります。

二分探索の2つの実装方法

C言語で二分探索を実装するには、主に次の2つの方法があります。両者の違いは、探索を行う関数を呼び出す方式だけです。

• 反復（イテレーション）を使う方法 − 関数内で while ループなどを回しながら、中央要素との一致を繰り返しチェックします。

• 再帰を使う方法 − 関数が異なる引数のセットで自分自身を繰り返し呼び出します。

方法1：反復（ループ）による実装

#include<stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
    int A[] = {0,2,6,11,12,18,34,45,55,99};
    int n=55;
    printf("%d is found at Index %d \n",n,iterativeBsearch(A,10,n));
    return 0;
}
int iterativeBsearch(int A[], int size, int element) {
    int start = 0;
    int end = size-1;
    while(start<=end) {
        int mid = (start+end)/2;
        if( A[mid] == element) {
            return mid;
        } else if( element < A[mid] ) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    return -1;
}

出力

55 is found at Index 8

方法2：再帰による実装

#include<stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
    if(start>end) return -1;
    int mid = (start+end)/2;
    if( A[mid] == element ) return mid;
    else if( element < A[mid] )
        return RecursiveBsearch(A, start, mid-1, element);
    else
        return RecursiveBsearch(A, mid+1, end, element);
}
int main() {
    int A[] = {0,2,6,11,12,18,34,45,55,99};
    int n=55;
    printf("%d is found at Index %d \n",n,RecursiveBsearch(A,0,9,n));
    return 0;
}

※ 再帰版では、再帰呼び出しの結果を必ず return で返すことが重要です。return を忘れると、正しいインデックスが呼び出し元に伝わらず、未定義の値が返されてしまいます。

出力

55 is found at Index 8

計算量と注意点

二分探索の時間計算量は O(log n) と非常に高速で、要素数が増えても探索回数は対数的にしか増えません。空間計算量は、反復版では O(1)、再帰版では呼び出しスタックの分だけ O(log n) が必要になります。

なお、二分探索は配列があらかじめソートされていることが前提のアルゴリズムです。未ソートの配列に対しては正しく動作しないため、事前に qsort などのソート処理を行っておきましょう。