二分探索・三分探索・黄金分割探索
各種探索を離散（整数）・連続（実数）それぞれで実装をまとめておく
二分探索
離散
いわゆるめぐる式二分探索。下の例ではng < okになっているが、ng > okになっても全く同じコードで記述できるのが強み。
言語や探索範囲によっては(ok+ng)//2の分子でオーバーフローしないよう注意が必要。
ok+(ng-ok)//2や(ok>>1)+(ng>>1)+(1&ok&ng)などで回避可能？
code:binary_int.py
ng = -1
ok = MAX
while abs(ok-ng) > 1:
mid = (ok+ng)//2
if isOK(mid) :
ok = mid
else:
ng = mid
連続
離散と同様。
code:binary_float.py
ng = 0
ok = MAX
while abs(ok-ng) > EPS:
mid = (ok+ng)/2
if isOK(mid) :
ok = mid
else:
ng = mid
三分探索
狭義凸関数の極値を求める。広義凸関数（極値以外に平坦な部分が存在する）では間違った値に収束する可能性がある。
離散
code:ternary_int.py
low, high = 0, MAX
midlow, midhigh = low, high
while abs(high-low) > 2:
midlow = (low*2+high)//3
midhigh = (low+high*2)//3
if f(midlow) < f(midhigh):
high = midhigh
else:
low = midlow
連続
code:ternary_float.py
low, high = 0, MAX
midlow, midhigh = low, high
while abs(high-low) > EPS:
midlow = (low*2+high)/3
midhigh = (low+high*2)/3
if f(midlow) < f(midhigh):
high = midhigh
else:
low = midlow
黄金分割探索
三分探索の分割点を黄金比にすることで、計算結果を使い回す。$ f(x) の計算コストが高いときにより効果を発揮する。収束速度もちょっと速い。
離散
フィボナッチ数列を利用する。MIN, MAXは答えとなり得ない領域から選び、f(x)は範囲外でINFを返す関数にする。
code:golden_int.py
low, midlow, midhigh, high = MIN, MIN+FIB-3, MIN+FIB-2, MIN+FIB-1 fl, fml, fmh, fh = f(low), f(midlow), f(midhigh), f(high)
for i in range(len(FIB)-1, 3, -1):
if fml < fmh:
midlow, midhigh, high = midlow - FIBi-4, midlow, midhigh fml, fmh, fh = f(midlow), fml, fmh
else:
low, midlow, midhigh = midlow, midhigh, midhigh + FIBi-4 fl, fml, fmh = fml, fmh, f(midhigh)
連続
黄金比を利用する。
code:golden_float.py
PHI = 1.61803398874989484 # (1 + √5) / 2
DIVPHI = 0.381966011250105151 # 1 / (1 + PHI)
low, high = 0, MAX
midlow = (low*PHI + high) * DIVPHI
midhigh = (low + high*PHI) * DIVPHI
fl, fml, fmh, fh = f(low), f(midlow), f(midhigh), f(high)
while abs(high-low) > EPS:
if fml < fmh:
midlow, midhigh, high = (low*PHI + midhigh) * DIVPHI, midlow, midhigh
fml, fmh, fh = f(midlow), fml, fmh
else:
low, midlow, midhigh = midlow, midhigh, (midlow + high*PHI) * DIVPHI
fl, fml, fmh = fml, fmh, f(midhigh)
補足
二分探索
離散であれば__len__と__getitem__を実装したクラスにbisectを組み合わせることで計算できる。
三分探索・黄金分割探索
f(low), f(midlow), f(midhigh), f(high)が(広義)単調増加のときは極値がlow～midlowの間にある → これを取り入れれば更に収束を速くできる
これを取り入れた場合三分探索と黄金分割探索で平均の収束速度同じくらいになりそう しらんけど
連続
連続verのabs(high-low) > EPSはlow, highが大きい場合に機能しない可能性がある。
ここをabs(high-low) / high > EPSとすれば誤差率での計算になる
float型の精度とか仕様的に、収束するループ回数の上限は決まってる（気がする）。二分探索なら53回、三分探索なら91回（くらい？）
verify問
離散
操作を$ n 回行ったときの落下時刻は$ t(n) = \frac{A}{\sqrt{n+1}}+Bn
$ 0 \le n \le A について$ t(n) を三分探索するか、
$ 0 \le n \le A について$ t'(n) = -\frac {A}{2\sqrt {n+1}^3} + B > 0 を二分探索するか
連続
$ x 年後に計算を始めた場合に計算にかかる時間は$ t(x) = x + \frac {P}{2^{x/1.5}}
$ 0 \le n \le P について$ t(n) を三分探索するか、
$ 0 \le n \le P について$ t'(x) = 1 - PZe^{-Zx} > 0 （ただし$ Z = \frac{2}{3}\log2 ）を二分探索するか