Ternary Search

Ternary Search(터너리 서치)는 함수의 최대나 최소점을 찾는 알고리즘으로 바이너리서치와 그 동작방법이 비슷하다.

터너리 서치로 최대점을 찾을 수 있는 함수는 최대점을 기준으로 왼쪽은 단조증가 오른쪽은 단조감소 해야한다.
마찬가지로 최소점을 찾을 수 있는 함수는 최소점을 기준으로 왼쪽은 단조감소 오른쪽은 단조증가 해야한다.

다시말해 지역 곡소점이나 극대점이 반드시 하나 존재해야 하고 이 점이 전역 최대나 최소점이 되어야 한다.

최대점을 찾아보자

a < b 인 두 점 a, b 가 있고 함수 f(x)의 최대점이 a와 b사이에 있다고 했을 때 a < a' < b' < b 인 a'과 b'을 잡을 수 있다.

이때 f(a') < f(b') 이라면 [a, a'] 구간은 단조증가하고 이 구간에 f(b') 보다 더 큰 값을 가지는 점은 없다.
따라서 a에 a'을 대입하여 탐색구간을 좁힐 수 있다.

반대로 f(a') > f(b') 인 경우 b에 b'을 대입하여 탑색구간을 좁힌다.

터너리 서치는 기본적으로 위의 아이디어를 가지고 있으며 [a, b] 구간을 3등분 하여 a'과 b'을 정한다. 따라서 한번의 탐색이 이루어질 때마다 탐색구간은 2/3으로 줄어들게 된다.


수도코드

// [left, right] 구간내에서 함수 f(x)가 최대인 x를 구한다.
double ternarySearch(int left, int right, function& f)
{

// 적당히 큰 수만큼 반복 -> 오차범위는 (right-left)*(2/3)^(반복횟수)

for (int i = 0; i < 1000; i++) {

double a = (left*2 + right) / 3;
double b = (left + right*2) / 3;

// 최소인 점을 찾으려면 if 문의 부호를 반대로 하면 된다.
if (f(a) < f(b))

left = a;

else

right = b;

}
return (left+right)/2;

}