【M5Stack Cardputer】加速度センサでボール物理シミュレーションを作る
Aru
Aru's テクログ（Aruaru0）
【Python】二分探索から三分探索へ！凸関数の極値探索と実装テンプレート解説
Aru
この記事では、三分探索について解説します。二分探索（Binary Search）は「単調性」のある関数の場合に利用しますが、三分探索は凸関数の場合に利用できるものです。この記事では、三分探索をPythonで実装するテンプレートを紹介します。
Contents
はじめに
二分探索が実装できるのであれば、三分探索は比較的スムーズに実装可能です。仕組みさえ理解すれば、Pythonですぐに実装できると思います。
二分探索の場合
二分探索は、データや関数に「単調増加」や「単調減少」といった単調性がある場合に利用するものです。単調増加とは値が増え続けるもの、単調減少とは値が減り続けるような性質のことです。
具体的な例としては、以下の問題があります。
問題1
問題
ソートされた整数配列 `arr` の中から、ターゲット値 `target` 以上の値が現れる最小のインデックスを探す
この問題では、配列がソートされているので、データが単調に並んでいることが担保されます。
ここで、条件を満たすインデックスの境界を `ok`、条件を満たさないインデックスの境界を `ng` と定義します。
このように `ok` と `ng` を用いると、「どちらの領域が条件を満たしているか」がコード上で明確になります。
Python での実装は以下のようになります。
def binary_search(arr: list[int], target: int) -> int:
# 初期値として、絶対に条件を満たさない ng と、満たす ok を設定します
ng = -1
ok = len(arr)
# 隣り合うまで範囲を狭めます
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
# 条件：注目している要素が target 以上であるか
if arr[mid] >= target:
ok = mid
else:
ng = mid
# 見つかった境界の要素が、実際に target と一致するか検証します
if ok < len(arr) and arr[ok] == target:
return ok
return -1
# 動作の確認
numbers = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(numbers, 7)) # 出力: 3このアルゴリズムは、要素数が2倍になっても探索回数が1回増えるだけです。
計算量は \(O(\log N)\) であり、巨大なデータに対しても一瞬で答えに到達できます。
単調性の崩壊と二分探索の限界
関数が単調増加や単調減少ではない場合を考えます。
例えば、二次関数のような「凸関数」です。
谷の形（下に凸）をした関数において、最小値を与える入力を探したいとします。
問題2
問題
関数 \(f(x) = (x – 2.5)^2 + 5\) を最小にする実数 \(x\) を求める
この関数は、 \(x = 2.5\) のときに最小値 \(5.0\) を取ります。
\(x < 2.5\) の範囲では単調減少であり、 \(x > 2.5\) の範囲では単調増加です。全体としては単調性はありません。
このような問題には二分探索を使うことができません。
探索範囲の中点 `mid` を調べたとしても、その値が最小値より左にあるのか右にあるのか、判断がつかないためです。
探索範囲を左右のどちらに絞ればよいのか、単一の点からでは情報が足りません。
探索範囲を3等分するアプローチ
ここで登場するのが三分探索です。
発想は簡単で、1つの点で情報が足りないなら、2つの点を使えば良いというものです。具体的には探索範囲 `[low, high]` を3等分するような2つの点、 `m1` と `m2` を設定します。
計算式は以下の通りです。
\(m_1 = low + \frac{high – low}{3}\)
\(m_2 = high – \frac{high – low}{3}\)
下に凸な関数において、この2つの点における関数の値 \(f(m_1)\) と \(f(m_2)\) を比較してみます。
もし \(f(m_1) < f(m_2)\) であれば、最小値が \(m_2\) より右側（値が増加している領域）に存在する可能性はありません。
したがって、探索範囲の右側1/3にあたる `[m2, high]` を切り捨てることができます。
新しい探索範囲は `[low, m2]` に狭まります。
逆に \(f(m_1) > f(m_2)\) であれば、最小値が \(m_1\) より左側（値が減少している領域）に存在する可能性はありません。
この場合は、探索範囲の左側1/3にあたる `[low, m1]` を切り捨てます。
新しい探索範囲は `[m1, high]` に狭まります。
このように、1回のステップで探索範囲を2/3に縮小していくことができます。
毎回範囲が定数倍で小さくなるため、計算量は「二分探索」と同様に \(O(\log N)\) です。
極めて高速に極値へと収束していきます。
実数と整数における実装形式
実装するにあたって、探索する値が「実数（浮動小数点数）」か「整数」かによって、注意すべきポイントが異なります。
それぞれの実装方法を整理してみました。
実数の場合の実装
実数を探索する場合、終了条件を `while high – low > eps`（`eps` は許容誤差）と書くのが直感的かもしれません。
ただ、浮動小数点数の精度限界により、無限ループに陥る危険性があります。
これを防ぐためには、ループ回数を固定してしまう書き方が安全です。
100回ほどループを回せば、探索範囲は \((2/3)^{100} \approx 2.46 \times 10^{-18}\) 倍になり、実用上十分な精度で極値が得られます。
def f(x: float) -> float:
# 最小値を求めたい目的関数（下に凸）
return (x - 2.5) ** 2 + 5.0
def ternary_search_real(low: float, high: float) -> float:
# 100回のループで十分な精度が得られます
for _ in range(100):
m1 = low + (high - low) / 3
m2 = high - (high - low) / 3
if f(m1) < f(m2):
high = m2
else:
low = m1
return low整数の場合の実装
整数を探索する場合、端点での切り捨て誤差が発生するため、少し注意が必要です。
範囲が狭くなったときに `m1` と `m2` が同じ値を指してしまい、無限ループや誤判定の原因になります。
そのため、探索範囲が十分に狭まる（例えば、差が3未満になる）までは「三分探索」で絞り込み、残った数個の候補から線形探索で答えを見つけるアプローチが確実です。
def f_int(x: int) -> int:
# 最小値を求めたい目的関数（下に凸、整数値を取る）
return (x - 42) ** 2 + 10
def ternary_search_int(low: int, high: int) -> int:
# 候補が3つ以上ある間は範囲を狭める
while high - low >= 3:
m1 = low + (high - low) // 3
m2 = high - (high - low) // 3
if f_int(m1) < f_int(m2):
high = m2
else:
low = m1
# 残った候補（low から high まで）の中から最小値を探す
ans = low
for x in range(low + 1, high + 1):
if f_int(x) < f_int(ans):
ans = x
return ansサンプルデータによる動作確認
提示した問題とテンプレートを組み合わせて、実際の挙動を確認してみます。
実数三分探索を実行するコードは以下の通りです。
# 実数三分探索の実行
result_x = ternary_search_real(-100.0, 100.0)
print(f"最小値を与える x: {result_x:.6f}")
print(f"最小値 f(x): {f(result_x):.6f}")このコードを実行すると、以下の出力が得られます。
出力結果
最小値を与える x: 2.500000
最小値 f(x): 5.000000期待通り、極めて正確に極値を特定できていることがわかります。
ループを100回回すだけで、実用上の誤差が無視できるレベルまで収束しています。
次に、整数三分探索を実行してみます。
# 整数三分探索の実行
result_x_int = ternary_search_int(0, 100)
print(f"最小値を与える x: {result_x_int}")
print(f"最小値 f_int(x): {f_int(result_x_int)}")出力は以下のようになります。
出力結果
最小値を与える x: 42
最小値 f_int(x): 10こちらも正しい極値をピンポイントで検出できました。
複雑な終了条件の判定に悩まされることなく、安全に実装を終えることができています。
おわりに
単調性がない関数であっても、凸性さえあれば「三分探索」によって極値を高速に求めることができます。二分探索だけでなく三分探索も知っておくと最適化問題などで重宝します。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
保有資格：CFP, マンション管理士、管理業務主任、宅建士など
