フィボナッチ探索とは？アルゴリズム解説と実装・性能比較（ITエンジニア向け）
エバープレイ編集部はじめに — フィボナッチ探索の概要
フィボナッチ探索（Fibonacci search）は、整数配列などのソートされた離散データに対して、有効な探索区間の分割位置をフィボナッチ数列に基づいて決定する探索アルゴリズムです。二分探索（binary search）と同様に順序付きデータに対して対数時間で探索できますが、分割点の決め方や比較回数の上限が特徴的です。古典的な探索アルゴリズムの一つであり、計算上の比較回数やメモリアクセスの性質に基づいて、特定の環境では有利になることがあります。
フィボナッチ数列と探索への応用
フィボナッチ数列は次のように定義されます：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。この数列の比は黄金比に漸近し、区間分割に利用すると特定の性質（前回の分割情報を活用できる等）を得られます。フィボナッチ探索は、探索対象の長さ n に対して、最小の F(k) 以上となる k を求め、探索区間の分割点を F(k-2) に相当する位置で決定して進めます。
アルゴリズムの手順（概要）
代表的な実装手順は以下の通りです。
- 探索対象配列の長さ n に対して、F(k) が n 以上となる最小の k を求める。
- 左端 L=0、右端 R=n-1 とし、試行位置 i = L + F(k-2) を計算する。
- 比較を行い、対象が試行位置より左側ならば R = i - 1、右側ならば L = i + 1 として k を更新（k = k-1 または k = k-2）する。これにより次の分割点は前回の計算結果を使って O(1) で得られる。
- 区間が狭くなるまで繰り返す。最終的に見つからなければ非存在を返す。
擬似コード
以下はわかりやすい擬似コードの例です。
1. k を満たす最小の整数（F(k) >= n）を求める。
2. offset = -1
3. while F(k) > 1:
i = min(offset + F(k-2), n-1)
if A[i] < key: k = k-1; offset = i
elif A[i] > key: k = k-2
else: return i
4. if F(k-1) and A[offset+1] == key: return offset+1
5. return -1 // 見つからない
時間計算量と比較回数
フィボナッチ探索の比較回数（最悪ケース）はおおむね O(log n) です。実際、F(k) ≈ φ^k / sqrt(5)（φは黄金比）なので k = O(log n)。二分探索と比べると、同じ n に対して比較回数の定数因子がほぼ同等です。ただし、分割比率の決定に定数回の前処理（フィボナッチ数列の生成）を要します。
二分探索との違い・利点と欠点
主な違いと比較点は以下のとおりです。
- 分割点の決定方法：二分探索は中央（配列の真ん中）で分割するのに対し、フィボナッチ探索はフィボナッチ数列に基づく不均等分割を行う。
- 比較回数の制御：フィボナッチ探索は比較回数を事前にフィボナッチ数で「パッケージ化」できるため、最悪比較回数の上限を精密に管理しやすい。
- 参照局所性：分割点の変化が隣接する要素へ移る場合があり、キャッシュやメモリアクセスのパターンによっては二分探索より有利なことがある。
- 実装の単純さ：二分探索の方が実装が簡潔であり、ほとんどの用途で充分高速であるため、一般的には二分探索が採用されやすい。
なぜフィボナッチ数を使うのか（直感）
フィボナッチ探索は、次の探索位置を以前の情報から O(1) の追加計算で得られる点が特徴です。つまり、新しい分割点は前回の分割点ともう一つ前の分割点の線形結合として得られるため、追加の乗除算をほとんど必要とせず、整数加減算で済む実装が可能です。古いハードウェアや乗除算が高コストだった環境では有利だった歴史的背景があります。
実装上の注意点（整数化と境界処理）
配列長 n とフィボナッチ数 F(k) の関係で k を選ぶ際、F(k) が n より大きい場合、配列境界を越えないよう min() を使うか、配列末尾の要素を重複させる処理（padding）を行う実装もあります。特に C/C++ のような低レベル言語ではオフバイワンや境界チェックを怠るとバグや不正メモリアクセスにつながります。また、F(k) が大きい場合はあらかじめフィボナッチ数列を 64 ビット整数で生成し、オーバーフローを避ける必要があります。
離散探索と連続最適化（黄金分割法との関係）
フィボナッチ探索は離散問題（配列探索）に焦点を当てますが、類似の考え方は連続関数の最適化でも用いられます。代表的なものが黄金分割法（golden-section search）で、これは単峰関数の区間縮小を行う手法で、区間分割比として黄金比を利用します。黄金分割法は連続領域での反復回数に対して極めて効率的で、フィボナッチ探索は離散の有限ステップに対する理想的分割を与えると理解できます。
実際の性能（理論 vs 実装）
理論的に両アルゴリズムは O(log n) ですが、実際のパフォーマンスは実装言語、CPU のキャッシュ特性、分岐予測、乗除算コストなどに依存します。現代の CPU では乗除算が非常に高速であり、二分探索の単純さが CPU キャッシュと分岐予測によって有利に働くことが多いです。一方で、メモリ性能やアクセスコストが従来の想定と異なる環境（例えば外部ストレージや分散ストレージ）では、アクセス回数やパターンを最適化できるフィボナッチ探索が有利になる場合があります。
実装例（Python による参考実装）
ここでは概念を示す簡潔な Python 実装例を説明します（配列は昇順ソート済み、見つからない場合は -1 を返す）。実際のコード化では境界チェックや型の安全性を十分考慮してください。
ポイントは次の通りです：フィボナッチ数列を先に生成し、ループ中で k を減らしていく。試行位置は offset + F(k-2) で計算し、F のインデックスに応じて更新する。
適用場面と実務上の判断基準
フィボナッチ探索が向いているケースと向かないケースを整理します。
- 向いているケース：
- 探索対象が静的で事前に長さ n が既知、比較回数を厳密に管理したい場合。
- 乗除算コストが高い組み込み環境やレガシーハードウェア。
- メモリ階層やアクセスパターンが特異で、キャッシュ局所性を意図的に調整したい場合。
- 向かないケース：
- 一般的な現代的アプリケーションでは二分探索で十分で実装も容易。
- データが動的に変化し、インデックス管理やパディングが煩雑になる場合。
拡張と派生：インターポレーション探索との比較
インターポレーション探索（interpolation search）は、探索キーの分布が均等に近い場合に平均 O(log log n) の性能を発揮することが知られています。これは位置推定に線形補間を用いる点でフィボナッチ探索や二分探索と異なります。分布に関する事前知識がある場合はインターポレーション探索が有利ですが、最悪ケースで O(n) になる可能性があるため注意が必要です。
実際の導入判断フロー（チェックリスト）
- 探索対象はソート済みか？（必須）
- 探索回数・比較回数の上限を厳密に管理する必要があるか？
- ハードウェアの演算コスト（乗除算やメモリアクセス）に制約があるか？
- 実装の簡潔さを優先するか、微妙な最適化を重視するか？
これらに照らしてフィボナッチ探索が有効と判断される場面で採用を検討してください。
まとめ
フィボナッチ探索は、古典的で理論的に興味深い探索手法です。現代の多くのケースでは二分探索の単純さが優先されますが、特定のハードウェア条件やメモリアクセスの特異条件ではフィボナッチ探索が有益になり得ます。アルゴリズムの理解を深めることで、より適切な探索アルゴリズムの選択が可能になります。
参考文献
- Fibonacci search technique — Wikipedia
- Binary search algorithm — Wikipedia
- Golden-section search — Wikipedia
- Donald E. Knuth, The Art of Computer Programming (公式ページ）
- Interpolation search — Wikipedia
投稿者プロフィール
