三分探索

2025年10月20日

三分探索

英語表記: Ternary Search

概要

三分探索（Ternary Search）は、探索アルゴリズムの一つであり、特に「アルゴリズムと計算量」の分野において、二分探索の概念を応用して最適化問題の解を高速に見つける手法です。通常の二分探索が単調なデータから特定の値を探索するのに対し、三分探索は探索範囲が単峰性（Unimodality）を持つ場合に、その最大値または最小値（極値）を発見することを目的としています。このアルゴリズムは、二分探索の「探索範囲を絞り込む」という強力なアイデアを継承しつつ、極値探索というより高度なニーズに対応するために進化しました。

詳細解説

三分探索が属する「探索アルゴリズム」のカテゴリーの中でも、これは非常に特殊で洗練された位置にあります。その主要な目的は、与えられた関数や配列の中から、最も優れた値、すなわち極値を効率よく特定することです。

目的と適用条件

三分探索は、探索対象が必ず単峰性を持っている場合にのみ適用可能です。単峰性とは、値が探索範囲のどこかまでは単調に増加し、その極値（ピーク）に達した後は単調に減少するか、あるいはその逆の形状を持つことを指します。この特性が保証されていなければ、三分探索は機能しません。この厳格な条件が、三分探索を二分探索の応用でありながら、異なる目的を持つ探索手法として明確に区別しています。

動作原理：なぜ三分割が必要なのか？

二分探索は、探索範囲を中央値で2分割し、どちらか半分を捨てます。これは、データが単調であるため、中央値と目標値を比較するだけで、残りの半分に目標値が存在しないと断定できるからです。

しかし、極値を探す場合、単純に2分割しただけでは情報が不足します。中央の値が「大きい」とわかっても、極値が中央値の左側にあるのか、右側にあるのかを判断するためには、さらに情報が必要です。

ここで三分探索の「三」が重要になります。三分探索では、現在の探索範囲 $[L, R]$ を均等に3つに分割するために、2つの比較点 $M_1$ と $M_2$ を設定します。

分割点の計算: $M_1$ は左から $1/3$ の位置、 $M_2$ は右から $1/3$ の位置に設定されます。
関数値の比較: 2つの分割点における関数値 $f(M_1)$ と $f(M_2)$ を計算し、比較します。

極値探索の判断ロジック（最大値の場合）
* $f(M_1) < f(M_2)$ の場合: $M_2$ の方が優れているため、極値は $M_1$ よりも右側の区間 $[M_1, R]$ に存在すると推定されます。単峰性の性質により、左端の区間 $[L, M_1]$ に極値が存在する可能性は排除されます。
* $f(M_1) > f(M_2)$ の場合: $M_1$ の方が優れているため、極値は $M_2$ よりも左側の区間 $[L, M_2]$ に存在すると推定されます。

このようにして、探索範囲は一度の操作で約 $1/3$ ずつ削減されていきます。二分探索が $1/2$ ずつ削減するのに対し、三分探索は少しだけ収束が遅くなりますが、極値探索という難しい課題に対して、非常に効率的な $O(\log N)$ の時間計算量を維持します。これは、アルゴリズムと計算量という観点から見ても、非常に優れた設計だと評価できますね。

具体例・活用シーン

三分探索は、情報科学の基礎である「探索アルゴリズム」の知識を、実世界の最適化問題に適用する際の強力なツールとなります。

活用シーン（最適化）
- 幾何学的最適化: 特定の形状や配置において、距離や面積が最大または最小になる点を求める問題で利用されます。例えば、与えられた線分上のどの点を選べば、他の点群からの距離の合計が最小になるか、といった問題です。
- コスト関数の最小化: 経営や工学において、あるパラメータ（生産量や材料費など）を変化させたときのコストが単峰性を示す場合、最小コストを実現するパラメータ値を迅速に特定するために利用されます。
比喩による理解：「最適な照明の位置探し」
あなたは美術館のキュレーターで、展示品に当てる照明の「最適な高さ」を探していると想像してください。照明の高さが低すぎても、高すぎても、展示品の美しさ（評価スコア）は低下し、ある特定の高さで最高の評価が得られることが経験的に分かっています（これが単峰性です）。

もし二分探索のように、現在の探索範囲（床から天井までの高さ）を真ん中で2分割し、中央の高さで評価スコアを測ったとしましょう。スコアが高くても、それが「ピークの途中なのか、もうピークを過ぎて下降している最中なのか」が判断できません。

そこで三分探索を使います。あなたは現在の範囲 $[L, R]$ の中で、2つの異なる高さ $M_1$ と $M_2$ に照明を設置し、専門家による評価スコア $S_1$ と $S_2$ を取得します。

例えば、$S_1 < S_2$ だった場合、あなたは「$M_2$ の方が優れているのだから、最適な高さは $M_1$ よりも高い位置にあるに違いない！」と確信できます。なぜなら、もし最適な高さが $M_1$ より低い位置にあったとしたら、$M_1$ の評価は $M_2$ よりも高くなっていたはずだからです。

このように、二つの比較点を持つことで、どちらの方向に最適解があるかを確実に判断し、探索範囲を $1/3$ に絞り込むことができるのです。これは、最適な配置を導き出すために、試行錯誤の回数を劇的に減らす、非常に賢い方法だと言えるでしょう。