フィボナッチ探索法

コンピュータサイエンスにおいて、フィボナッチ探索法は、分割統治アルゴリズムを使用してソートされた配列を探索する方法であり、フィボナッチ数列の助けを借りて可能性のある場所を絞り込みます。^[1]ソートされた配列を2つの同じサイズの部分に分割し、そのうちの1つをさらに調べるバイナリ探索と比較すると、フィボナッチ探索では、配列を連続するフィボナッチ数列のサイズを持つ2つの部分に分割します。平均して、これにより実行される比較が約4%多くなりますが、 ^[2]アクセスされた配列要素のインデックスを計算するために加算と減算のみが必要であるという利点があります。一方、従来のバイナリ探索では、フィボナッチ探索が最初に公開された当時はあまり一般的ではなかったビットシフト（ビット演算を参照）、除算、または乗算が必要です。^[1]これらの操作は。フィボナッチ探索の平均および最悪の場合の複雑度はO（log n）です（ビッグオー記法を参照）。

フィボナッチ数列には、数がその前の 2 つの数の合計であるという特性があります。したがって、数列は繰り返し加算することで計算できます。連続する 2 つの数の比率は、黄金比1.618 に近づきます... バイナリ検索は、検索領域を均等な部分 (1:1) に分割することで機能します。フィボナッチ検索は、より単純な操作を使用しながら、1:1.618 に近づく部分に分割できます。

検索対象の要素のアクセス メモリ ストレージが均一でない場合 (つまり、ストレージ ロケーションへのアクセスに必要な時間がアクセスするロケーションによって異なる場合)、フィボナッチ検索はバイナリ検索よりも、ストレージ ロケーションへのアクセスに必要な平均時間をわずかに短縮できるという利点があります。検索を実行するマシンに直接マップされたCPU キャッシュがある場合、アクセスされる要素は少数のキャッシュ ラインに集まる傾向があるため、バイナリ検索ではキャッシュ ミスが多くなる可能性があります。この問題は、配列を 2 の累乗にならない部分に分割することで軽減されます。データが磁気テープ上に保存され、シーク時間が現在のヘッド位置によって異なる場合、シーク時間が長くなると比較回数が増えることのトレードオフにより、フィボナッチ検索と同様に偏った検索アルゴリズムになる可能性があります。

フィボナッチ探索は、ジャック・キーファー（1953）による、区間内の単峰関数の最大値または最小値を検索するアルゴリズムである黄金分割探索から派生したものです。 ^[3]

k をフィボナッチ数列の配列Fの要素として定義します。n = F _{m は}配列のサイズです。n がフィボナッチ数でない場合は、F mを_nより大きいFの最小の数とします。

フィボナッチ数列は、k ≥ 0、F ₁ = 1、F ₀ = 1のとき、F _{k +2} = F _{k +1} + F _kとして定義されます。

項目が順序付けられた番号のリストに含まれているかどうかをテストするには、次の手順に従います。

1. k = mと設定します。
2. k = 0の場合、停止します。一致するものはありません。項目は配列内にありません。
3. 項目をF _{k −1}内の要素と比較します。
4. 項目が一致した場合は停止します。
5. 項目がエントリF _{k −1}より小さい場合は、位置F _{k −1} + 1からnまでの要素を破棄します。k = k − 1に設定し、手順2に戻ります。
6. 項目がエントリF _{k −1}より大きい場合は、位置 1 からF _{k −1}までの要素を破棄します。残りの要素を 1 からF _{k −2}まで再番号付けし、k = k − 2に設定して、手順 2 に戻ります。

代替実装（Knuth著「Sorting and Searching」より^[4]）：

キーが昇順K ₁ < K ₂ < ... < K _NであるレコードテーブルR ₁、R ₂、 ...、R _Nが与えられた場合、アルゴリズムは与えられた引数Kを検索します。N +1= F _{k +1と仮定します。}

ステップ1. [初期化] i ← F _k、p ← F _{k −1}、q ← F _{k −2}（アルゴリズム全体を通して、pとq は連続したフィボナッチ数になります）

ステップ 2. [比較] K < Ki_の場合はステップ 3に進み、K > Kiの場合_はステップ 4に進み、K = Ki_の場合はアルゴリズムが正常に終了します。

ステップ3. [ iを減少させる] q =0の場合、アルゴリズムは失敗して終了します。それ以外の場合は、( i、p、q ) ← ( i − q、q、p − q ) に設定します（これにより、pとq がフィボナッチ数列で1つ前に戻ります）。その後、ステップ2に戻ります。

ステップ4. [ iを増やす] p =1の場合、アルゴリズムは失敗して終了します。それ以外の場合は、( i、p、q ) ← ( i + q、p − q、 2 q − p ) に設定し（これにより、pとq がフィボナッチ数列で2つ前に戻ります）、ステップ2に戻ります。

上で示したアルゴリズムの 2 つのバリエーションは、常に現在の間隔を大きいサブ間隔と小さいサブ間隔に分割します。ただし、元のアルゴリズム^[1]では、ステップ 4 で新しい間隔を小さいサブ間隔と大きいサブ間隔に分割します。この方法の利点は、新しいiが古いiに近くなり、磁気テープ上での検索を高速化するのにより適していることです。

• 検索アルゴリズム

• Lourakis, Manolis. 「C 言語でのフィボナッチ検索」 。2007年1 月 18 日閲覧。上記のアルゴリズムを実装します (Ferguson のオリジナルのものではありません)。