Algorithm Guidecomplexity: O(log log n) avg

보간 탐색 (Interpolation Search)

값의 분포가 균등하다고 가정하고 Target의 '위치'를 비례 계산으로 추정합니다. 균등 분포에서는 이진 탐색보다 빠르지만, 편향된 분포에서는 최악 O(n)까지 퇴화할 수 있습니다.

01 Explore How It Works

Interactive Step-by-Step

HOVER OR SCROLL

Interpolation Search

보간 탐색 시작. 값이 균등하게 분포한다고 가정하고, 목표 위치를 비례식으로 추정해 O(log log n)까지 줄입니다.

Logic Node1 / 6

Live Python

# target: 45

1def interpolation_search(arr, target):

# low: 0

2 low = 0

# high: 9

3 high = len(arr) - 1

4 while low <= high and arr[low] <= target <= arr[high]:

5 if arr[high] == arr[low]:

6 break

7 pos = low + ((target - arr[low]) *

8 (high - low)) // (arr[high] - arr[low])

9 if arr[pos] == target:

10 return pos

11 elif arr[pos] < target:

12 low = pos + 1

13 else:

14 high = pos - 1

15 return -1

02 Understand It Simply

For Everyone

🔑Analogy

사전에서 'ㅎ'을 찾을 때 뒤쪽을 바로 펼치듯, 값으로 위치를 추정하는 것.

💡In Plain Words

값의 분포가 고르다고 보고 target의 위치를 비례로 추정해 건너뜁니다.

균등 분포에선 이진 탐색보다 빨라요.

📍Where It's Used

–균등 분포 정렬 데이터(전화번호부 등)

03 Python Implementation

A clean, readable reference implementation of the core logic of 보간 탐색 (Interpolation Search).

core_implementation.py

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high and arr[low] <= target <= arr[high]:
        if arr[high] == arr[low]:
            break
        pos = low + ((target - arr[low]) *
                     (high - low)) // (arr[high] - arr[low])
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1