Algorithm Guidecomplexity: O(log n)

지수 탐색 (Exponential Search)

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

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

TAP OR HOVER

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))

Guide Progress0%