균일하게 n개의 데이터가 분포되어 정렬된 배열이 있을 경우 이진 탐색보다 성능이 좋음 ex) 10, 12, 13, 15, 18, 22, 25, 26, 27, 30, ... => 성능 ↑ 10, 102, 192, 375, 462, 1777, ... => 성능 ↓
이진 탐색은 탐색 대상의 값과 상관없이 무조건 절반씩 잘라서 비교하지만, 보간 탐색은 탐색 대상이 앞쪽에 있을 경우 앞쪽부터 탐색을 진행
선형 보간법을 이용해 탐색 위치를 결정함
보간 탐색 방법
탐색을 시작할 위치를 공식을 통해 알아낸다.
해당 위치에 탐색 대상이 있을 경우 해당 위치 값을 반환한다.
해당 위치의 값이 탐색 대상보다 작으면 탐색 대상의 왼쪽을 다시 탐색하고, 크다면 오른쪽을 탐색한다.
탐색 대상을 찾거나 탐색범위가 0이 될 때까지 1~3 과정을 반복한다.
탐색 위치 지정 공식 직선의 방정식 : \(y = mx + c\) 를 이용 (y : 배열의 값, x : 배열 값의 인덱스, m : 기울기) low, high, a를 방정식에 넣어서 계산 \(arr[high] = m * high + c\) \(arr[low] = m * low + c\) \(arr[a] = m * a + c\)
두 점의 좌표를 알면 기울기를 구할 수 있음 \((low, arr[low]), (high, arr[high])\) 일 때, 기울기 : \(\frac{arr[high]-arr[low]}{high-low}\)
\(arr[a] = m * a + c\) 수식에서 c를 제외하고 왼쪽으로 옮기면 아래와 같이 수식이 된다. \(c = arr[a] - m * a\) 찾고자 하는 인덱스는 음수가 나올 수 없으므로 이를 \(arr[low] = m * low + c\)에 대입한다. \(arr[low] = m * low + arr[a] - m * a\) \(m * a = m * low + arr[a] - arr[low]\) \(a = low + \frac{(arr[a] - arr[low])}{m}\) m(기울기)은 위에서 구했으므로 대입하면 최종적으로 아래와 같이 수식이 나온다. $$a = low + \frac{(arr[a] - arr[low])}{(arr[high]-arr[low])} * (high - low)$$
arr[a] : 탐색 대상 a : 찾고자하는 인덱스
구현
기본 구현 [InterpolationBasic.java]
package Search.Interpolation;
public class InterpolationBasic {
public static int search(int[] arr, int start, int end, int target) throws Exception {
// 찾고자하는 값의 인덱스
int targetIndex = 0;
// 재귀 탈출 조건
// 재귀가 계속해서 호출될수록 아래 targetIndex - 1 또는 targetIndex + 1에 의해
// 값이 배열의 범위에서 벗어날 수 있음
if (arr[start] > target || arr[end] < target) {
throw new Exception("데이터를 찾을 수 없습니다.");
}
// 데이터의 모든 값이 중복된 경우 (10, 10, 10, 10, 10 등)
// targetIndex를 구할 때 DivideByZero 예외가 발생하게 되므로 처음과 끝을 확인
else if (arr[start] == arr[end]) {
if (arr[start] == target) {
return start;
}
else {
throw new Exception("데이터를 찾을 수 없습니다.");
}
}
// double로 계산 후 다시 int로 변환한 이유는 아래와 같다.
// 10 ~ 30까지의 범위에서 12값을 찾을 때, 아래 수식은
// ((12 - 10) / (30 - 10) * (20 - 0)) + 0 => (1/10 * 20) + 0 이 된다.
// 그러나, 1/10은 int에서는 0으로 변환되므로 최종값은 0이 되기 때문에 double형으로 먼저 계산 후 int형으로 바꿔주는 방식으로 구현해야 한다.
targetIndex = (int)((double)(target-arr[start]) / (arr[end] - arr[start]) * (end - start)) + start;
System.out.println("targetIndex : " + targetIndex);
if (arr[targetIndex] == target) {
return targetIndex;
}
else if (target < arr[targetIndex]) {
return search(arr, start, targetIndex - 1, target);
}
else {
return search(arr, targetIndex + 1, end, target);
}
}
}
테스트 [InterpolationBasicMain.java]
package Search.Interpolation;
import java.util.Arrays;
public class InterpolationBasicMain {
private static final int MAX_COUNT = 30;
public static void main(String[] args) throws Exception {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
Arrays.sort(arr);
System.out.println("배열 값 출력");
for(int i : arr) {
System.out.print(i + " ");
}
System.out.println();
int search = InterpolationBasic.search(arr, 0, arr.length - 1, 5);
System.out.println("탐색완료 : " + search);
}
}
결과
이진 탐색과 보간 탐색 비교
데이터 100개를 임의생성한 후 특정 값을 찾는데 몇 번의 탐색 인덱스값을 설정했는지 확인
package Search;
import Search.BinarySearch.BinarySearchBasic;
import Search.Interpolation.InterpolationBasic;
import java.util.Arrays;
public class SearchCompareTest {
private static final int MAX_COUNT = 100;
public static void main(String[] args) throws Exception {
int[] arr = new int[MAX_COUNT];
for(int i=0; i<MAX_COUNT; i++) {
// 0 ~ MAX_COUNT 범위내의 난수를 생성
arr[i] = (int)(Math.random() * MAX_COUNT);
}
Arrays.sort(arr);
int searchBinary = BinarySearchBasic.search(arr, 0, arr.length - 1, 10);
System.out.println("searchBinary : " + searchBinary);
System.out.println();
int searchInter = InterpolationBasic.search(arr, 0, arr.length - 1, 10);
System.out.println("searchInter : " + searchInter);
}
}
결과
이진 탐색의 경우 무조건 절반씩 잘라서 탐색하기 때문에 7번의 탐색만에 찾았지만, 보간 탐색의 경우 탐색 대상이 앞쪽에 있는지, 뒷쪽에 있는지 확인한 후 탐색 인덱스를 결정하기 때문에 성능이 더 좋다. (데이터 산포가 적을 경우에만)
