【筆記】Ternary Search 三分搜

  • 【用途】對於一個二次函數 (可能是 🙂 或 🙁 ),我們可以利用三分搜找出其最低點或最高點。
  • 【實作】逼近法求近似解
    • 設定左界 (l) 和右界 (r)
    • 任意選中間兩點 ml 和 mr
    • 重複逼近求解
  • 【練習】Codeforces 578C. Weakness and Poorness題解
int l = -10000;
int r = 10000;
int iterations = 100;
for (int i = 0; i < iterations; i++){
    double mr = (l + r) / 2.0;
    double ml = (l + mr) / 2.0;
    // f( ): 目標函數
    if (f(ml) < f(mr)) r = mr;
    else l = ml;
}
分享本文 Share with friends