Algorithm Guidecomplexity: O(log₃ n)

삼진 탐색 (Ternary Search)

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

01 Explore How It Works

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 Understand It Simply

For Everyone

🔑Analogy

구간을 세 토막으로 나눠 한 번에 두 지점을 보는 것.

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 삼진 탐색 (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)