ternary search

삼분 탐색 (Ternary Search)

삼분 탐색은 볼록함수에서 극값 혹은 최대/최솟값을 찾을 때 사용할 수 있는 테크닉이다.

이분 탐색은 함수가 항상 단조 증가/감소할 때만 쓸 수 있었지만, 삼분탐색의 경우 보다 더 복잡한 곳에도 사용이 가능하다.

메커니즘의 특성상, 최솟값이 아닌데 평탄한 구간이 존재할 경우 삼분 탐색을 쓸 수가 없으므로 이에 유의한다.

한쪽은 순감소, 반대쪽은 순증가라면 삼분 탐색을 사용할 수 있다. (최솟값 찾을 수 있을때)

구현

삼분탐색의 구현에 필요한 변수들은 다음과 같다.

• 시작점 (range_start) : 삼분탐색 구간의 시작점
• 끝점 (range_end) : 삼분탐색 구간의 끝점
• left : 시작점에 가중치를 더 둔 점 ((2 * range_start + range_end) / 3)
• right : 끝점에 가중치를 더 둔 점 ((range_start + 2 * range_end) / 3)

삼분 탐색의 구현은 아래와 같다.

long long range_start = 1, range_end = 1e9;

while (range_start + 3 <= range_end) {
  long long left = (2 * range_start + range_end) / 3;
  long long right = (range_start + 2 * range_end) / 3;

  long long costL = calculateCost(left);
  long long costR = calculateCost(right);

  if (costL < costR) {
    range_end = right;
  } else {
    range_start = left;
  }
}

위 로직을 실행한 결과, 최솟값을 가질 수 있는 위치는 start ~ end 사이에 있음이 보장된다.

최후에 이 구간을 이용해 정답을 구한다.