【C言語】二分探索を再帰関数で実装するプログラムを解説

2023年9月13日

この記事では、C言語で二分探索を再帰関数を使って実装する方法を解説します。

目次から探す

二分探索のアルゴリズム

二分探索は、ソートされた配列やリストから特定の要素を効率的に探索するアルゴリズムです。

以下では、二分探索の手順を説明します。

二分探索の手順の説明

ソートされた配列やリストの中央の要素を選択します。
選択した要素と目的の要素を比較します。
選択した要素が目的の要素と一致した場合、探索終了です。
選択した要素が目的の要素よりも大きい場合、探索範囲を中央よりも前の部分に絞ります。
選択した要素が目的の要素よりも小さい場合、探索範囲を中央よりも後ろの部分に絞ります。
新たな範囲で再び中央の要素を選択し、手順2から繰り返します。
探索範囲がなくなるまで繰り返します。

再帰関数を使った二分探索の実装方法の説明

再帰関数を使った二分探索の実装では、上記の手順を再帰的に呼び出すことで探索を行います。

以下では、再帰関数を使った二分探索の実装方法を説明します。

二分探索の再帰関数の実装

以下に、再帰関数を使った二分探索のサンプルコードを示します。

#include <stdio.h>
int binarySearch(int arr[], int low, int high, int target) {
    if (low > high) {
        return -1; // 要素が見つからなかった場合
    }
    
    int mid = (low + high) / 2;
    
    if (arr[mid] == target) {
        return mid; // 要素が見つかった場合
    }
    else if (arr[mid] > target) {
        return binarySearch(arr, low, mid - 1, target); // 中央よりも前の部分を探索
    }
    else {
        return binarySearch(arr, mid + 1, high, target); // 中央よりも後ろの部分を探索
    }
}
int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 12;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result == -1) {
        printf("要素が見つかりませんでした。\n");
    }
    else {
        printf("要素が見つかりました。インデックス: %d\n", result);
    }
    
    return 0;
}

コードの解説

上記のサンプルコードでは、binarySearchという再帰関数を定義しています。

この関数は、ソートされた配列 arr の中から target という要素を探索します。

関数内部では、まず low と high の中央の要素を mid として計算します。

そして、arr[mid] と target を比較し、一致するかどうかを判定します。

一致する場合は、mid を返して探索を終了します。

一致しない場合は、arr[mid] が target よりも大きいか小さいかによって、再帰的に探索範囲を絞っていきます。

探索範囲がなくなるまで繰り返し、要素が見つかった場合はそのインデックスを、見つからなかった場合は -1 を返します。

上記のサンプルコードでは、配列 {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} から要素 12 を探索しています。

結果として、要素が見つかった場合はそのインデックスを、見つからなかった場合は「要素が見つかりませんでした。」と表示されます。

以上が、再帰関数を使った二分探索の実装方法の解説です。

【C言語】 二分探索を再帰関数で実装するプログラムを解説