Algorithm Guidecomplexity: O(log n)

지수 탐색 (Exponential Search)

인덱스를 2의 지수로 확장(1, 2, 4, 8, …)하여 Target을 포함하는 구간을 빠르게 특정한 뒤, 해당 구간에서 이진 탐색을 수행합니다. 길이를 알 수 없는 무한/무경계 스트림 탐색에 강점이 있습니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Exponential Search

지수 탐색 시작. 인덱스를 2의 지수(i=1, 2, 4, 8…)로 늘려가며 목표 구간을 찾은 뒤, 그 안에서 이진 탐색을 수행합니다.

Logic Node1 / 8

Live Python

# target: 45

1def exponential_search(arr, target):

2 if arr[0] == target:

# i: 1

3 return 0

4 i = 1

5 while i < len(arr) and arr[i] <= target:

6 i *= 2

7 return binary_search(arr, target,

8 i // 2, min(i, len(arr) - 1))

9def binary_search(arr, target, low, high):

10 while low <= high:

11 mid = (low + high) // 2

12 if arr[mid] == target:

13 return mid

14 elif arr[mid] < target:

15 low = mid + 1

16 else:

17 high = mid - 1

18 return -1

02 쉽게 이해하기

For Everyone

🔑비유

1, 2, 4, 8…로 보폭을 두 배씩 늘려 범위를 빠르게 잡는 것.

💡쉽게 말하면

인덱스를 2배씩 키워 target이 든 구간을 특정한 뒤, 그 구간에서 이진 탐색합니다.

길이를 모르는 데이터에 강해요.

📍어디에 쓰나

–무한·무경계 스트림
–길이 미상 정렬 데이터

03 파이썬 구현 코드

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

core_implementation.py

def exponential_search(arr, target):
    if arr[0] == target:
        return 0
    i = 1
    while i < len(arr) and arr[i] <= target:
        i *= 2
    return binary_search(arr, target,
                         i // 2, min(i, len(arr) - 1))

04 자주 묻는 질문

FAQ

지수 탐색 (Exponential Search)란 무엇인가요?+

지수 탐색 (Exponential Search)의 시간복잡도는 어떻게 되나요?+

지수 탐색 (Exponential Search)의 시간복잡도는 O(log n) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

지수 탐색 (Exponential Search)은(는) 어디에 사용하나요?+

무한·무경계 스트림, 길이 미상 정렬 데이터.

지수 탐색 (Exponential Search)를 쉽게 비유하면?+

1, 2, 4, 8…로 보폭을 두 배씩 늘려 범위를 빠르게 잡는 것.

→ 탐색 전체 보기Related

🔍선형 탐색 (Linear Search)

O(n)

🔍이진 탐색 (Binary Search)

O(log n)

🔍점프 탐색 (Jump Search)

O(√n)

🔍보간 탐색 (Interpolation Search)

O(log log n) avg

🔍삼진 탐색 (Ternary Search)

O(log₃ n)

🔍피보나치 탐색 (Fibonacci Search)

🔍A* 탐색 (A-Star Search)

O(E)