[알고리즘, C] 보간 탐색(Interpolation Search) 구현

<보간 탐색(Interpolation Search) 구현>

https://sevenshards.tistory.com/22

[알고리즘, C] 이진 탐색(Binary Search) 구현

기존의 이진 탐색 구현에서 약간의 변경만 하면 된다.

 

[InterpolationSearch.c]

/*
* 알고리즘 - 보간 탐색(Interpolation Search)
* 파일명: InterpolSearch.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-27
* 이전 버전 작성 일자:
* 버전 내용: 기존에 구현한 이진 탐색 알고리즘을 기반으로 보간 탐색 구현
* 이전 버전 내용:
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int InterpolationSearch(int arr[], int first, int last, int target)
{
	int pos; // 보간 탐색에서는 중앙값이 아닌 비례식에서 유도된 식을 기반으로 탐색 위치를 정한다.

	// first보다 last가 커지는 경우 = 값을 찾지 못한 경우 - 재귀의 탈출 조건 첫 번째.
	if (first > last)
		return -1;

	// 비례식에 의해 유도된 식을 기반으로 한 탐색 위치를 설정한다.
	pos = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

	// 탐색 시작
	// 찾은 경우 인덱스 값을 반환 - 재귀의 탈출 조건 두 번째.
	if (target == arr[pos])
		return pos;

	// 값을 찾지 못한 경우
	else if (target > arr[pos]) // 목표로 한 값이 탐색 시작 위치의 값보다 크다면
		return InterpolationSearch(arr, pos + 1, last, target); // pos 까지는 비교했으므로 pos의 다음 인덱스부터 last까지 다시 탐색
	else // 목표로 한 값이 탐색 시작 위치의 값보다 작다면
		return InterpolationSearch(arr, first, pos - 1, target); // pos까지는 비교했으므로 first부터 pos의 바로 이전 인덱스까지 다시 탐색 
}


int main()
{
	int arr[] = { 1,3,5,7,9 };
	int result;

	// 배열 내에 없는 2를 찾기 위해 호출 -> 문제가 생긴다
	result = InterpolationSearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);

	if (result == -1)
		printf("찾지 못함\n");
	else
		printf("%d 번째 인덱스에 있음\n", result);

	return 0;
}

 

[보간 탐색의 이해]

보간 탐색 또한 이진 탐색처럼 재귀적으로 구성하여 사용할 수 있는 탐색 알고리즘 중 하나다.
단, 이진 탐색처럼 인덱스의 중앙값을 탐색 위치로 지정하여 시작하는 것이 아니다.

탐색 대상에 가까운 곳에서부터 탐색을 하는 알고리즘이다.
보간 탐색은 저장된 데이터의 값과 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정한다.
그래서 탐색 위치는 비례식에 의해 유도된 식을 사용하여 정한다.

[보간 탐색의 탐색 위치 식 유도]

$low$와 $high$는 탐색 대상의 시작과 끝을 나타내는 인덱스 값이다.
그리고 $A$는 $arr[high]-arr[low]$이며, 맨 마지막 인덱스와 맨 처음 인덱스가 가지고 있는 값의 차다.
$s$는 내가 찾고자 하는 데이터가 저장된 인덱스다.
$Q$는 $arr[s] - arr[low]$로 내가 찾고자 하는 인덱스에 저장된 값과 맨 처음 인덱스가 가지고 있는 값의 차다.

보간 탐색에서는 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정한다.

그래서 다음과 같은 비례식을 구성할 수 있다.

$A:Q = (high-low) : (s-low)$

이 식에서 찾고자하는 값은 s이므로 비례식을 s에 대한 식으로 정리하면 다음과 같이 된다.

$s=\frac AQ(high-low) + low$

여기서 찾는 데이터의 값이 arr[s]이고 이를 x라고 하면 최종적으로는 다음과 같은 식이 만들어진다.

$s=\frac{x-arr[low]}{arr[high]-arr[low]}(high-low)+low$

그래서 $x$에 찾는 값을 삽입하면 탐색 위치 $s$를 구할 수 있는 식이 된다.
여기서 주목해야 하는 부분이 있다.

오차율을 최소화하기 위해서 정수형 나눗셈이 아닌 ‘실수형 나눗셈’을 수행한다는 사실이다.
그리고 이는 보간 탐색의 단점이 되기도 한다.

 

[보간 탐색의 장단점 - 이진 탐색과의 비교]

1) 장점
- 빠른 탐색 속도

이진 탐색과 비교한다면 평균적으로 더 빠른 탐색 속도를 제공.
단, 배열 내에 저장된 데이터들이 고르게 분포되어 있고 값들이 겹치지 않게 있을 경우에 해당한다.

- 탐색 위치

보간 탐색은 배열 내의 값들의 분포를 고려해서 예상 위치를 계산한다.
그래서 이진 탐색보다 찾고자 하는 값에서 더 가까운 위치에서 탐색을 시작한다.

- 적은 비교 횟수

이진 탐색은 항상 배열의 중앙에 있는 값부터 비교한다.
하지만 보간 탐색은 예상 탐색 위치를 기반으로 범위를 좁혀나가므로 비교 횟수가 줄어들 수 있다.

2) 단점
- 배열에 저장된 데이터 값의 분포 상태에 의존

배열에 저장된 값들의 분포가 불균형하거나 값이 많이 겹치는 경우, 성능의 저하가 일어난다.
이런 경우는 이진 탐색을 사용하는 것이 낫다.
- 무작위 접근에는 효율이 떨어진다

보간 탐색은 규칙에 따라 탐색 범위를 축소하기 때문에 배열의 무작위 접근에는 적합하지 않다.
이럴 때는 해시 테이블 등의 다른 자료구조를 고려하는 것이 좋다.
- 추가 연산 비용

이진 탐색과 달리 보간 탐색은 예상 위치를 계산하는 추가 연산이 필요하다.
특히 ‘실수형 나눗셈’을 하므로 이진 탐색보다는 더 많은 계산을 필요로 하게 된다.
그래서 일부 상황에서는 이진 탐색보다 느릴 수도 있다.

 

[현재 구현한 코드의 문제점 - 탐색 대상이 존재하지 않는 경우]

만약 위의 코드에서 InterpolationSearch(arr, 1, 4, 2)를 수행하면 어떻게 될까?
인덱스 1~4의 범위 내에서 2의 탐색을 수행하게 되는 함수를 호출하는 상황이다.
위의 식을 대입하면 s는 0이 되고, 코드 상에서는 pos가 0이 된다.
이 부분은 전혀 문제가 되지 않는, 정상적인 동작이다.
인덱스 1~4의 범위에서 현재 최대값은 9, 최솟값은 3이 된다.
그런데 찾고자 하는 값은 2다. 따라서 3~9 사이에 있는 값 자체가 아니게 된다.
문제가 생기는 부분은 바로 여기다.

// 찾은 경우 인덱스 값을 반환 - 재귀의 탈출 조건 두 번째.
if (target == arr[pos])
	return pos;

// 값을 찾지 못한 경우
else if (target > arr[pos]) // 목표로 한 값이 탐색 시작 위치의 값보다 크다면
	return InterpolationSearch(arr, pos + 1, last, target); // pos 까지는 비교했으므로 pos의 다음 인덱스부터 last까지 다시 탐색
else // 목표로 한 값이 탐색 시작 위치의 값보다 작다면
	return InterpolationSearch(arr, first, pos - 1, target); // pos까지는 비교했으므로 first부터 pos의 바로 이전 인덱스까지 다시 탐색

조건에 의해서 else if에 있는 문장이 실행된다.

그래서 맨 처음에 호출한 InterpolationSearch(arr, 1,4 2)를 그대로 다시 호출하게 되는 것.
함수의 탈출 조건을 만족하지 못하면서 계속 호출하게 되어 무한 루프에 걸리게 된다.

 

[InterpolationSearch.c - 문제 해결 버전]

/*
* 알고리즘 - 보간 탐색(Interpolation Search)
* 파일명: InterpolSearch.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-27
* 이전 버전 작성 일자:
* 버전 내용: 기존에 구현한 이진 탐색 알고리즘을 기반으로 보간 탐색 구현
* 이전 버전 내용:
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int InterpolationSearch(int arr[], int first, int last, int target)
{
	int pos; // 보간 탐색에서는 중앙값이 아닌 비례식에서 유도된 식을 기반으로 탐색 위치를 정한다.

	// 찾고자 하는 값이 배열의 첫 번째 값보다 작거나 마지막 값보다 큰 경우 - 보간 탐색에서의 재귀 탈출 조건 첫 번째.
	if (target < arr[first] || target > arr[last])
		return -1;

	// 비례식에 의해 유도된 식을 기반으로 한 탐색 위치를 설정한다.
	pos = ((double)(target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;

	// 탐색 시작
	// 찾은 경우 인덱스 값을 반환 - 재귀의 탈출 조건 두 번째.
	if (target == arr[pos])
		return pos;

	// 값을 찾지 못한 경우
	else if (target > arr[pos]) // 목표로 한 값이 탐색 시작 위치의 값보다 크다면
		return InterpolationSearch(arr, pos + 1, last, target); // pos 까지는 비교했으므로 pos의 다음 인덱스부터 last까지 다시 탐색
	else // 목표로 한 값이 탐색 시작 위치의 값보다 작다면
		return InterpolationSearch(arr, first, pos - 1, target); // pos까지는 비교했으므로 first부터 pos의 바로 이전 인덱스까지 다시 탐색 
}


int main()
{
	int arr[] = { 1,3,5,7,9 };
	int result;

	// 배열 내에 없는 2를 찾기 위해 호출 -> 문제가 생긴다
	result = InterpolationSearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 2);

	if (result == -1)
		printf("찾지 못함\n");
	else
		printf("%d 번째 인덱스에 있음\n", result);

	return 0;
}

 

[새로운 재귀의 탈출 조건]

재귀의 탈출 조건을 변경하였다.
보간 탐색에서는 탐색 대상이 존재하지 않을 경우에는 탐색 대상의 값은 탐색 범위 내에 있는 값을 넘어선다.

이와 같은 사실을 근거로 하여 조건을 수정하면 된다.

 

// 찾고자 하는 값이 배열의 첫 번째 값보다 작거나 마지막 값보다 큰 경우 - 보간 탐색에서의 재귀 탈출 조건 첫 번째.
if (target < arr[first] || target > arr[last])
	return -1;