보간 탐색 (Interpolation Search)

보간 탐색 (Interpolation Search)

정렬된 배열에서 찾고자 하는 값의 위치를 데이터 분포에 따라 추정하여 탐색하는 알고리즘으로, 균일 분포 데이터에서 이진 탐색보다 빠름

목적: 균일 분포 데이터의 빠른 탐색, 이진 탐색 개선

특징: 데이터 분포 고려, 위치 추정, 정렬 필수

위치 추정 공식: pos = low + ((key - arr[low]) / (arr[high] - arr[low])) × (high - low)

동작 과정

시간 복잡도

• •균일 분포: O(log log n) 평균
• •비균일 분포: O(n) 최악 (편향된 데이터)

공간 복잡도: O(1)

장점: 균일 분포에서 이진 탐색보다 빠름, 직관적

단점: 비균일 분포에서 성능 저하, 정렬 필수, 오버플로우 주의

적용사례: 전화번호부, 사전, 데이터베이스 인덱스(균일 분포)

비교: 보간(O(log log n)/균일) vs 이진(O(log n)/범용) vs 지수(O(log i)/앞쪽)

연관: 이진 탐색, 탐색 알고리즘, 정렬된 배열