二分探索と三分探索の数学的な解説とバグらせない実装方法 - Qiita

この記事の内容 この記事では二分探索と三分探索の解説及びその実装について記します。 この記事の特徴として数学的に厳密な説明を心がけているので、直感的な説明を読みたい場合は参考記事を見るなどするようにお願いします。 前置き 以下では二分探索(or三分探索)で考える関数の定義域xを整数または実数の集合上での閉区間としますが、実際には全順序集合(有理数の集合などを含む)上での閉区間であれば定義域とすることができます。 また、パソコン上においては実数のような連続集合であっても離散的に扱うので、以下の集合は全て離散集合であることに注意が必要です。 二分探索 二分探索とは x(元の個数は$n$)で単調増加(or減少)関数$f$が定義されている時、$f(x^*)=t$となる$x^* \in$ xが存在するかを$O(\log n)$で探索するアルゴリズムのことです。1 以下では暗黙的に$f$を単調増加関数

[razokulover]

三分探索これかー