Algorithm Guidecomplexity: O(log log n) avg

보간 탐색 (Interpolation Search)

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

01보간 탐색 (Interpolation Search)

알고리즘 작동 원리 탐색

보간 탐색을 시작합니다. 값이 고르게 퍼져 있다고 보고, 목표가 있을 만한 자리를 비례식으로 곧장 짚습니다.

45는 5부터 98까지의 범위에서 앞쪽에 놓입니다. 비례식이 짚은 자리는 인덱스 3 — 이진 탐색의 한가운데보다 목표에 가깝습니다.

짚은 자리의 값은 34로 45보다 작습니다. 목표는 오른쪽에 있으니 그 뒤부터 다시 셈합니다.

이번엔 남은 구간의 첫 값이 곧 목표라, 비례식이 그 자리를 정확히 가리킵니다.

짚은 자리가 바로 45 — 두 번 만에 목표를 찾았습니다.

탐색 완료 · 45는 인덱스 4에 있습니다. 고르게 퍼진 값에 강하지만, 한쪽에 쏠린 값에서는 O(n)까지 나빠집니다.

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

1 / 6

02 쉽게 이해하기

For Everyone

🔑핵심 동작

값이 고르게 분포한다고 보고 목표가 있을 위치를 비례식으로 추정합니다. 가정이 맞으면 이분 탐색보다 빠릅니다.

💡쉽게 말하면

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

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

📍어디에 쓰나

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

03 파이썬 구현 코드

보간 탐색 (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