삼분 탐색 (Ternary Search)

정의

삼분 탐색 (Ternary Search) 은 단봉 (unimodal) 함수의 극값 (최대 / 최소) 을 O(log N) 에 찾는 알고리즘. 구간을 3등분하는 두 점 m1, m2 에서 함수값을 비교, 극값이 없는 1/3 을 매번 제거한다.

단봉: 최대점이 하나이고, 그 전까지 증가, 그 후 감소 (또는 반대). Binary Search 이 배열에서 값을 찾는다면, 삼분 탐색은 함수 그래프에서 극값 위치를 찾는다.

문제 상황과 동기

함수 f(x) 의 극값 위치를 알고 싶다 (f(x) 미분 불가 또는 비용 높음).

• naive: 모든 x 를 시도. O(N) 또는 무한 (실수 구간).
• 삼분 탐색: 단봉이면 구간 1/3 씩 제거. O(log N).

예: f(x) = -(x-5)^2 + 10 의 최대값. 미분하면 x=5 지만, f 가 복잡하면 미분 어려움. 삼분 탐색은 함수값만 평가해서 극값을 찾는다.

핵심 통찰: “m1, m2 에서 f(m1) < f(m2) 이면, 극대는 [m1, hi] 에 있다”.

실무: 물리 시뮬레이션, 비용 함수 최적화, 게임 AI 파라미터 튜닝.

시각화

핵심 아이디어

invariant: 극값은 항상 [lo, hi] 구간 안에 있다. 매 단계에서 구간을 3등분: m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3.

초기: lo = 구간 시작, hi = 구간 끝
while hi - lo > eps:
    m1 = lo + (hi - lo) / 3
    m2 = hi - (hi - lo) / 3
    if f(m1) < f(m2):  # 최대 찾기
        lo = m1        # 극대는 [m1, hi] 에
    else:
        hi = m2        # 극대는 [lo, m2] 에
return (lo + hi) / 2

최소 찾기는 조건 반대. 각 단계마다 구간 길이가 2/3 배.

알고리즘

최대값 찾기 (실수 구간)

ternary_max(lo, hi, f):
    for _ in range(100):  # log_{3/2}(구간) 회면 충분
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2
    return (lo + hi) / 2

최소값 찾기

ternary_min(lo, hi, f):
    for _ in range(100):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) > f(m2):
            lo = m1
        else:
            hi = m2
    return (lo + hi) / 2

정수 구간

ternary_max_int(lo, hi, f):
    while hi - lo > 2:
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2
    return max(f(lo), f(lo+1), ..., f(hi)) 에서 argmax

구현

// f(x) = -(x-5)^2 + 10 의 최대값 위치
#include <bits/stdc++.h>
using namespace std;
double f(double x) {
  return -(x - 5.0) * (x - 5.0) + 10.0;
}
int main() {
  double lo, hi;
  cin >> lo >> hi;
  for (int i = 0; i < 100; i++) {
      double m1 = lo + (hi - lo) / 3.0;
      double m2 = hi - (hi - lo) / 3.0;
      if (f(m1) < f(m2)) lo = m1;
      else               hi = m2;
  }
  double x = (lo + hi) / 2.0;
  cout << fixed << setprecision(6) << x << " " << f(x) << "\n";
}

# f(x) = -(x-5)^2 + 10 의 최대값 위치
def f(x):
  return -(x - 5.0) ** 2 + 10.0
​
lo, hi = map(float, input().split())
for _ in range(100):
  m1 = lo + (hi - lo) / 3.0
  m2 = hi - (hi - lo) / 3.0
  if f(m1) < f(m2):
      lo = m1
  else:
      hi = m2
x = (lo + hi) / 2.0
print(f"{x:.6f} {f(x):.6f}")

// f(x) = -(x-5)^2 + 10 의 최대값 위치
import java.util.*;
public class Main {
  static double f(double x) {
      return -(x - 5.0) * (x - 5.0) + 10.0;
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      double lo = sc.nextDouble(), hi = sc.nextDouble();
      for (int i = 0; i < 100; i++) {
          double m1 = lo + (hi - lo) / 3.0;
          double m2 = hi - (hi - lo) / 3.0;
          if (f(m1) < f(m2)) lo = m1;
          else               hi = m2;
      }
      double x = (lo + hi) / 2.0;
      System.out.printf("%.6f %.6f\n", x, f(x));
  }
}

0.0 10.0

5.000000 10.000000

4.5 5.5

5.000000 10.000000

복잡도

실수 구간 [0, 10^9] 에서도 100 회 반복이면 10^-15 정밀도.

변형 / 활용

함정

1. 단봉 가정 위반

f(x) 에 극값이 여러 개면 틀린 답. 예: sin(x) 는 단봉 아님.

2. f(m1) == f(m2) 처리

부동소수점 오차로 거의 같을 때 무한 루프 / 느림. eps 또는 고정 횟수 로 종료.

// 잘못: while (abs(hi - lo) > 1e-9)  // 무한 가능
// 올바름: for (int i = 0; i < 100; i++)

3. 이분 탐색과 혼동

• 이분 탐색: 정렬된 배열에서 값 찾기, O(log N).
• 삼분 탐색: 단봉 함수에서 극값 찾기, O(log N).

목적이 다름.

4. 정수 구간 끝 처리

정수 삼분은 hi - lo <= 2 일 때 직접 확인.

while (hi - lo > 2) { ... }
// 남은 lo, lo+1, lo+2, hi 직접 비교

이분 탐색 vs 삼분 탐색

BOJ 연습 문제

참고

• Binary Search
• Parametric Search
• Golden-section search (수학적 최적 분할 비율)