C言語で学ぶ二分探索の実装方法：再帰呼び出しと反復処理を徹底解説

二分探索（Binary Search）とは

二分探索（バイナリサーチ）は、ソート済みの配列から特定の要素（ターゲット値）の位置を効率的に見つけ出すための探索アルゴリズムです。二分探索を適用する前に、配列があらかじめソートされている必要がある点に注意しましょう。

このアルゴリズムは、「対数探索」「バイナリチョップ」「半区間探索」などの名前でも知られています。

二分探索の仕組み

二分探索では、探索したい要素と配列の中央にある要素を比較し、その比較結果に応じて次の処理を決定します。

• ケース1： 探索要素 ＝ 中央要素 → 要素が見つかったので、そのインデックスを返します。
• ケース2： 探索要素 ＞ 中央要素 → 中央より右側の部分配列（middle+1 ～ n）を対象に探索を続けます。
• ケース3： 探索要素 ＜ 中央要素 → 中央より左側の部分配列（0 ～ middle-1）を対象に探索を続けます。

比較のたびに探索範囲が半分になるため、計算量は O(log n) となり、大規模なデータに対しても高速に動作します。

アルゴリズムの手順

パラメータ：initial_value（開始位置）、end_value（終了位置）

ステップ1：middle = initial_value + end_value / 2; により配列の中央要素を求める。
ステップ2：もし middle == element ならば「要素が見つかった」としてインデックスを返す。
ステップ3：もし middle > element ならば、end_value = middle - 1 として関数を再度呼び出す。
ステップ4：もし middle < element ならば、start_value = middle + 1 として関数を再度呼び出す。
ステップ5：終了。

実装方式：反復型と再帰型

二分探索アルゴリズムの関数実装には、同じ処理を繰り返し呼び出す方式が使われます。その呼び出し方には以下の2種類があります。

• 反復呼び出し（Iterative）： 同じコードブロックをループで何度も繰り返し実行する方式です。スタックオーバーフローの心配がなく、メモリ効率に優れています。
• 再帰呼び出し（Recursive）： 同じ関数を自分自身の中で繰り返し呼び出す方式です。コードが簡潔になり、アルゴリズムの論理構造を直感的に表現できます。

反復呼び出しによる二分探索の実装プログラム

サンプルコード

#include <stdio.h>
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
    while (start_index <= end_index){
        int middle = start_index + (end_index - start_index) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] < element)
            start_index = middle + 1;
        else
            end_index = middle - 1;
    }
    return -1;
}
int main(void){
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 16;
    int found_index = iterativeBinarySearch(array, 0, n-1, element);
    if(found_index == -1 ) {
        printf("Element not found in the array ");
    }
    else {
        printf("Element found at index : %d", found_index);
    }
    return 0;
}

実行結果

Element found at index : 4

この例では、配列 {1, 4, 7, 9, 16, 56, 70} の中から値 16 を探索しています。結果として、インデックス 4 の位置で要素が見つかりました。

再帰呼び出しによる二分探索の実装プログラム

サンプルコード

#include <stdio.h>
int recursiveBinarySearch(int array[], int start_index, int end_index, int element){
    if (end_index >= start_index){
        int middle = start_index + (end_index - start_index) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] > element)
            return recursiveBinarySearch(array, start_index, middle-1, element);
        return recursiveBinarySearch(array, middle+1, end_index, element);
    }
    return -1;
}
int main(void){
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 9;
    int found_index = recursiveBinarySearch(array, 0, n-1, element);
    if(found_index == -1 ) {
        printf("Element not found in the array ");
    }
    else {
        printf("Element found at index : %d", found_index);
    }
    return 0;
}

実行結果

Element found at index : 3

こちらの例では、同じ配列から値 9 を探索しています。再帰的に範囲を絞り込んでいき、最終的にインデックス 3 の位置で要素が見つかりました。

まとめ

二分探索は、ソート済み配列に対して O(log n) の時間計算量で高速に要素を検索できる強力なアルゴリズムです。反復型はループ処理でメモリを節約でき、再帰型はコードがシンプルで理解しやすいという特徴があります。どちらの実装方法を選ぶかは、プロジェクトの要件や可読性の優先度に応じて判断するとよいでしょう。