二分法検索を C言語の再帰関数で実装する方法は?

2年 ago
桜, 春樹
1 minute

二分法検索を再帰的に実現する考え方は次のようになります。

  1. まず、ソートされた配列、対象要素、配列の開始位置と終了位置を引数として受け取る関数定義。
  2. 関数内で、始点より終点が小さい場合、つまり探索する対象が配列に存在しない場合は-1を返す
  3. 配列の真ん中の位置 `mid` を計算し、配列の中央にある要素と、検索する要素を比較する。
  4. 中間要素が探索している要素と等しければ、探索完了で、midを返す。
  5. 中央要素が探索目標の要素より大きければ、左半分の要素で2分探索を継続する。つまり、同じ開始位置で関数を再帰呼び出し、終了位置はmid-1とする。
  6. 中間の要素が検索対象よりも小さい場合、右半分で二分探索を続行します。つまり、関数を再帰的に呼び出し、開始位置をmid+1に変更し、終了位置は同じままにします。
  7. 3 から 6 の手順を、探索要素が見つかるか、開始位置が終了位置を超えるまで繰り返す。

再帰を用いた二分法検索のサンプルコードを以下に示します。

#include <stdio.h>

int binarySearch(int arr[], int target, int start, int end) {
    if (start > end) {
        return -1;
    }

    int mid = (start + end) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, start, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, end);
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int target = 5;
    int result = binarySearch(arr, target, 0, sizeof(arr) / sizeof(arr[0]) - 1);
    if (result == -1) {
        printf("Element not found\n");
    } else {
        printf("Element found at index %d\n", result);
    }
    return 0;
}

バイナリサーチ関数を定義してバイナリサーチを実現し、main関数でその関数を呼び出して検索を行います。結果はElement found at index 2となり、指定された配列内の検索対象要素が見つかり、そのインデックスの位置が2であることを示します。

bannerAds