三分探索
概要
極大値や極小値を求めるのに用いる
テクニック
黄金分割(
https://naoyat.hatenablog.jp/entry/2012/01/04/231801)
区間を三等分するのではなく、探索領域を 1:φ, φ:1 にそれぞれ分割するx1,x2 を選ぶ。φ = (1+√5) / 2
取得した値が次に再利用可能 → インタラクティブ問題でクエリ数を減らすのに有用
区間が実数ではなく整数である場合、区間の長さをフィボナッチ数から1を引いた値にすれば、整数丸め誤差がなくなる
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/053-04.jpg