최대치를 포함하는 후보 구간 [lo, hi]에 대해 삼등분 하는 두 위치 (2lo + hi) / 3 , (lo + 2hi) / 3
만약 두 값 중 오른쪽 값이 더 크면, [lo, 왼쪽값] 에는 최대치가 있을 수 없다.
그래서 lo를 왼쪽값으로 바꿔줄 수 있다.
그 반대의 경우도 마찬가지.
이를 이용하는 것이다.
최대치
// 우리가 최대치를 찾고 싶어하는 함수
double f(double x);
// [lo, hi] 구간에서 f(x)가 최대치를 갖는 x를 반환한다.
double ternary(double lo, double hi)
{
for (int iter = 0; iter < 100; ++iter)
{
double a = (2 * lo + hi) / 3.0;
double b = (lo + 2 * hi) / 3.0;
if (f(a) > f(b))
hi = b;
else
lo = a;
}
return (lo + hi) / 2.0;
}
최소치
// 우리가 최소치를 찾고 싶어하는 함수
double f(double x);
// [lo, hi] 구간에서 f(x)가 최소치를 갖는 x를 반환한다.
double ternary(double lo, double hi)
{
for (int iter = 0; iter < 100; ++iter)
{
double a = (2 * lo + hi) / 3.0;
double b = (lo + 2 * hi) / 3.0;
if (f(a) < f(b))
hi = b;
else
lo = a;
}
return (lo + hi) / 2.0;
}