Ternary search (Convex upwards)
(Mylib/Algorithm/ternary_search_upwards.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

References

Verified with

• test/aoj/0323/main.ternary.test.cpp

Code

#pragma once
#include <functional>

namespace haar_lib {
  template <typename T = double, typename Func = std::function<T(T)>>
  T ternary_search_upwards(T lb, T ub, const Func &f, int LOOP_COUNT = 100) {
    T t1 = 0, t2 = 0;

    while (LOOP_COUNT--) {
      t1 = lb + (ub - lb) / 3;
      t2 = lb + (ub - lb) / 3 * 2;

      if (f(t1) > f(t2)) {
        ub = t2;
      } else {
        lb = t1;
      }
    }

    return lb;
  }
}  // namespace haar_lib

#line 2 "Mylib/Algorithm/ternary_search_upwards.cpp"
#include <functional>

namespace haar_lib {
  template <typename T = double, typename Func = std::function<T(T)>>
  T ternary_search_upwards(T lb, T ub, const Func &f, int LOOP_COUNT = 100) {
    T t1 = 0, t2 = 0;

    while (LOOP_COUNT--) {
      t1 = lb + (ub - lb) / 3;
      t2 = lb + (ub - lb) / 3 * 2;

      if (f(t1) > f(t2)) {
        ub = t2;
      } else {
        lb = t1;
      }
    }

    return lb;
  }
}  // namespace haar_lib

Back to top page