二分探索

二分探索

 

関連問題

  • 食塩水 (ABC034)
  • Enclose All (ABC151)
    座標問題における二分探索の基本、及び浮動小数点演算時の注意点を理解するのに良い問題です。
  • Yakiniku Optimization Problem (ABC157)
    Enclose Allを1段階難しくした問題です。

三分探索

関数の極値を探索するアルゴリズム。
極値が1つしかない関数に適用した場合、最大値または最小値が求まる。(e.g. 二次関数)

微分してf'(x)=0となるxを二分探索しても答えは求まる。
しかし、三分探索を用いた方が微分の手間が省け、計算ミスやエンバグの可能性を減らすことができる。

(参考) 三分探索 – 忘れても大丈夫

例題

ムーアの法則