Algorithm Guidecomplexity: O(log₃ n)

삼진 탐색 (Ternary Search)

구간을 3등분하여 두 개의 중간 지점(mid1, mid2)으로 세 구간을 한 번에 판별합니다. 이진 탐색보다 재귀 깊이는 얕지만 반복당 비교 횟수가 많아, 실제로는 유니모달 함수의 극값 탐색에 주로 사용됩니다.

01삼진 탐색 (Ternary Search)

알고리즘 작동 원리 탐색

삼진 탐색을 시작합니다. 구간을 셋으로 나눠 두 지점을 한 번에 견주고, 남길 구간 하나를 고릅니다.

열 칸을 셋으로 나눈 두 경계는 인덱스 3과 6입니다. 두 자리를 한 번에 확인합니다.

두 경계의 값은 34와 67. 45는 그 사이에 있으니 가운데 구간만 남기고 양쪽을 버립니다.

남은 두 칸에서 같은 일을 반복합니다. 경계는 인덱스 4와 5입니다.

앞 경계의 값이 45 — 목표와 일치합니다. 구간을 두 번 나누고 끝났습니다.

탐색 완료 · 45는 인덱스 4에 있습니다. 한 번에 두 곳을 견주는 탓에 실제로는 이진 탐색이 더 빠르고, 주로 볼록 함수의 극값 찾기에 씁니다.

Live Python

# target: 45

1def ternary_search(arr, low, high, target):

# low: 0

2 if low > high:

# high: 9

3 return -1

4 mid1 = low + (high - low) // 3

5 mid2 = high - (high - low) // 3

6 if arr[mid1] == target:

7 return mid1

8 if arr[mid2] == target:

9 return mid2

10 if target < arr[mid1]:

11 return ternary_search(arr, low, mid1 - 1, target)

12 elif target > arr[mid2]:

13 return ternary_search(arr, mid2 + 1, high, target)

14 else:

15 return ternary_search(arr, mid1 + 1, mid2 - 1, target)

1 / 6

02 쉽게 이해하기

For Everyone

🔑핵심 동작

구간을 셋으로 나눠 두 지점을 보고 한 토막을 버립니다. 단봉 함수의 극값을 찾는 데 씁니다.

💡쉽게 말하면

구간을 3등분해 두 지점으로 범위를 좁힙니다.

정렬 탐색보다는 주로 볼록(유니모달) 함수의 극값 찾기에 써요.

📍어디에 쓰나

–유니모달 함수의 최적값 찾기

03 파이썬 구현 코드

삼진 탐색 (Ternary Search)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

def ternary_search(arr, low, high, target):
    if low > high:
        return -1
    mid1 = low + (high - low) // 3
    mid2 = high - (high - low) // 3
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    if target < arr[mid1]:
        return ternary_search(arr, low, mid1 - 1, target)
    elif target > arr[mid2]:
        return ternary_search(arr, mid2 + 1, high, target)
    else:
        return ternary_search(arr, mid1 + 1, mid2 - 1, target)