Algorithm Guidecomplexity: O(log n)

지수 탐색 (Exponential Search)

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

01지수 탐색 (Exponential Search)

알고리즘 작동 원리 탐색

지수 탐색을 시작합니다. 한 칸, 두 칸, 네 칸… 두 배씩 멀리 짚어 목표가 든 구간을 찾은 뒤 그 안에서 이진 탐색을 합니다.

첫 자리의 값 12는 아직 45보다 작습니다. 짚는 거리를 두 배로 늘립니다.

두 칸 뒤의 값 23도 45에 못 미칩니다. 다시 두 배로 늘립니다.

네 칸 뒤의 값은 45로 목표와 같지만, 여기서 멈추지 않고 규칙대로 한 번 더 늘립니다.

여덟 칸 뒤의 값 89는 45를 넘어섰습니다. 목표는 방금 지나온 구간 안에 있습니다.

좁혀진 구간에서 이진 탐색을 시작합니다. 한가운데 값 67은 45보다 커서 뒤쪽 절반을 버립니다.

남은 구간의 한가운데 값이 45 — 목표와 일치합니다.

탐색 완료 · 45는 인덱스 4에 있습니다. 길이를 모르는 배열에서도 앞부분만 짚어 구간을 잡을 수 있습니다.

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

1 / 8

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)