Algorithm Guidecomplexity: O(log n)

지수 탐색 (Exponential Search)

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

01 Explore How It Works

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

For Everyone

🔑Analogy

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

💡In Plain Words

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

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

📍Where It's Used

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

03 Python Implementation

A clean, readable reference implementation of the core logic of 지수 탐색 (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 Frequently Asked Questions

FAQ

What is 지수 탐색 (Exponential Search)?+

What is the time complexity of 지수 탐색 (Exponential Search)?+

The time complexity of 지수 탐색 (Exponential Search) is O(log n). Follow the step-by-step visualization to see exactly why.

Where is 지수 탐색 (Exponential Search) used?+

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

What's a simple analogy for 지수 탐색 (Exponential Search)?+

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

→ Searching — see allRelated

🔍선형 탐색 (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)

Guide Progress0%