보간 탐색(Interpolation Search)

오늘의 포스팅은 탐색 시리즈 중 보간 탐색(Interpolation Search)입니다!

보간탐색은 지난 이진탐색(Binary Search)의 개선된 버전이라고 할 수 있습니다!

 

# 동작과정 

보간 탐색(Interpolation Search)은 보간(Interpolation)이라는 단어에서 유추할 수 있는데요

보간(Interpolation)은 이미 알고 있는 값들 사이에서 미지의 값을 추정하는 것을 의미하는데,

보간 탐색(Interpolation Search)은 이를 기반으로 탐색 값이 정렬된 데이터 내 어디에 위치할지 비례적으로 추정하는 탐색법입니다!

이로인해 탐색할 값과 해당 위치는 비례한다는 가정에 기반합니다

 

동작과정은 이진탐색과 유사한데요 

이미 정렬된 데이터에서만 적용할 수 있으며,

특히 데이터가 균등하게 분포되어 있을 경우, 효율적으로 탐색할 수 있습니다

1) 보간값 == 타겟

-> 탐색 종료

2) 보간값  > 타겟 

-> 보간값 왼쪽 데이터셋 탐색

3) 보간값  < 타겟 

-> 보간값 오른쪽 데이터셋 탐색

 

(이진탐색은 보간값이 아니라 중앙값이라는 점에서만 차이가 있습니다!)

이진탐색은 균등하게 절반씩 분할하여 탐색했다면,

보간탐색은 불균등하게 분할하여 탐색합니다

 

보간값은 아래와 같습니다! 비례식을 이용하여 계산됩니다

예시와 같이

10,20,30,40,50 처럼 완벽히 균등하게 정렬된 데이터에서는 한번의 탐색으로 값을 찾을 수 있습니다!

 

# Python 코드

보간값과 타겟값의 조건별로 구현합니다

타겟값을 찾을시, 타겟값의 인덱스를 반환하며

탐색할 타겟값이 없다면, -1을 반환하도록 하였습니다

def interpolation_search(data, target):

    low = 0

    high = len(data) - 1

    # 탐색 조건: low가 high 이하이고 target이 범위 내에 있어야 함

    while low <= high and target >= data[low] and target <= data[high]:

        # 보간 공식에 따라 보간값 계산

        pos = low + ((target - data[low]) * (high - low) // (data[high] - data[low]))

        if data[pos] == target: # 보간값 == 타겟

            return pos  # 탐색 성공, 값의 인덱스 반환

       

        elif data[pos] < target: # 보간값 < 타겟

            low = pos + 1 # 탐색 범위를 오른쪽으로 좁힘

       

        else: # 보간값 > 타겟

            high = pos - 1 # 탐색 범위를 왼쪽으로 좁힘

    # 탐색값이 없을시 -1반환

    return -1

 

# 성능분석 - 시간복잡도

보간탐색의 시간복잡도는 총 3가지 경우로 확인할 수 있습니다 

 

최선의 경우(Best Case)

O(1)

완벽하게 균등할 경우 한번의 보간식을 통해 값을 찾을 수 있습니다 

 

평균적인 경우(Average Case)

O(loglogn)

 

이진탐색의 경우에는 절반씩 탐색하므로 O(logn)의 시간복잡도를 보이지만

보간탐색에서는 절반이 아닌 더 세밀하게 범위를 줄여가며 탐색하므로  O(loglogn)의 시간복잡도를 보입니다! 

균등한 경우에는 이진탐색보다 더 빠르게 탐색할 수 있겠죠!

 

최악의 경우(Worst Case) 

O(n)

 

값이 매우 불균등한 경우에는 아무리 보간식을 통해 계산을 해도 값을 하나씩 비교하는 순차탐색과 동일하므로 O(n)의 시간복잡도로 이루어 집니다

예) 1,2,3,4,5,999999

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.