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

2023-09-132024-06-05

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

目次から探す

2分探索のアルゴリズム

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

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

2分探索の手順の説明

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

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

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

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

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

以下に、再帰関数を使った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;
}