Algorithm Guidecomplexity: O(log₃ n)

삼진 탐색 (Ternary Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Ternary Search

삼진 탐색 시작. 구간을 3등분해 두 개의 mid(mid1, mid2)로 세 구간을 한 번에 판별합니다. O(log₃ n).

Logic Node1 / 6

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)

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)