フィボナッチ数を活用した分割統治法でソート済み配列を検索するC++プログラム

このC++プログラムでは、フィボナッチ数を利用した分割統治法（Divide and Conquer）による探索を実装します。フィボナッチ数を使ってデータ配列の中間位置（mid）を計算し、目的の要素を効率よく検索します。この手法の時間計算量はO(log n)です。

フィボナッチ探索とは

フィボナッチ探索は、二分探索と同じくソート済み配列を対象とする探索アルゴリズムです。二分探索が配列の中央を基準に検索範囲を半分ずつ絞り込むのに対し、フィボナッチ探索はフィボナッチ数列（0, 1, 1, 2, 3, 5, 8, 13, ...）を利用して比較位置を決定します。除算を使わず加算だけで比較位置を求められるため、除算コストが高い環境では二分探索より有利に働くことがあります。

アルゴリズム

開始
    ソートされた状態でデータを配列に格納する。
    検索する要素を入力として受け取る。
    FibonacciSearch()関数を呼び出す。
    「start + fib[index-2]」の式で中間値（mid）を計算する。
    検索対象がmidインデックスの値と一致すれば、結果を表示してmainへ戻る。
    midインデックスの値より小さければ、左側の部分配列で処理を続ける。
    midインデックスの値より大きければ、右側の部分配列で処理を続ける。
    計算されたmidの値がstartまたはendと等しくなった場合、その要素は配列内に存在しない。
終了

サンプルコード

#include<iostream>
using namespace std;
void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) {
    int i, mid;
    mid = start+fib[index-2];
    if(item == a[mid]) {
        cout<<"\n item found at "<<mid<<" index.";
        return;
    } else if(item == a[start]) {
        cout<<"\n item found at "<<start<<" index.";
        return;
    } else if(item == a[end]) {
        cout<<"\n item found at "<<end<<" index.";
        return;
    } else if(mid == start || mid == end) {
        cout<<"\nElement not found";
        return;
    } else if(item > a[mid])
        FibonacciSearch(a, mid, end, fib, index-1, item);
    else
        FibonacciSearch(a, start, mid, fib, index-2, item);
}
main() {
    int n, i, fib[20], a[10]={3, 7, 55, 86, 7, 15, 26, 30, 46, 95};
    char ch;
    fib[0] = 0;
    fib[1] = 1;
    i = 1;
    while(fib[i] < 10) {
        i++;
        fib[i] = fib[i-1] + fib[i-2];
    }
    up:
        cout<<"\nEnter the Element to be searched: ";
        cin>>n;
        FibonacciSearch(a, 0, 9, fib, i, n);
        cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
        cin>>ch;
        if(ch == 'y' || ch == 'Y')
            goto up;
        return 0;
}

※フィボナッチ探索はソート済みの配列を前提とするアルゴリズムです。実際に使用する際は、配列の要素が昇順に並んでいることを確認してください。

実行結果

Enter the Element to be searched: 26
item found at 6 index.
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 45
item not found
Do you want to search more...enter choice(y/n)?n

まとめ

フィボナッチ探索は、フィボナッチ数列を活用してソート済み配列を効率的に検索する手法です。時間計算量は二分探索と同じO(log n)であり、除算を一切使わずに中間位置を決定できる点が大きな特徴です。再帰的に検索範囲を絞り込むことで、目的の要素を高速に特定できます。