Chapter 11. 탐색의 이해와 보간 탐색

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

우리는 이전에 '순차 탐색'과 '이진 탐색'에 대해 배웠습니다. 따라서 이번에 탐색에 대해 배운다고 하면 순차 탐색이나 이진 탐색 이외의 다른 탐색 알고리즘들을 배울 것이라고 생각하기 쉽습니다. 하지만 이번에 배울 탐색에 대한 내용은 사실 '트리'에 대한 뒷 이야기에 더 가깝습니다.

 

탐색은 굳이 따지자면 알고리즘보다는 자료구조에 더 가까운 주제입니다. 왜냐하면 효율적인 탐색을 위해서는 효율적인 탐색을 가능하게 하는 효율적인 저장 방법에 대해 필수적으로 고민해야 하기 때문입니다. 그런데 효율적인 탐색이 가능한 가장 대표적인 저장 방법은 '트리'입니다. 때문에 지금부터 배우게 될 탐색에 관한 내용들은 대부분 트리의 연장선상에 놓이게 됩니다.

 

참고로 다음 Chapter에서 배우게 될 '테이블과 해쉬'도 탐색과 관련 있는 내용입니다.

---

우선 '보간 탐색' 알고리즘을 먼저 소개하고자 합니다. 보간 탐색 알고리즘은 이진 탐색 알고리즘의 단점을 보완하고자 나온 알고리즘입니다. 이진 탐색 알고리즘은 찾고자 하는 데이터가 배열의 가장 앞에 있어도 배열의 중간부터 확인해가며 범위를 차차 줄여나갑니다. 이는 전화번호부에서 김경수 씨를 찾는데 그 두꺼운 전화번호부의 중간 부분부터 열어 확인하는 것과 같습니다. 하지만 정말로 그런 식으로 김경수 씨를 찾는 사람은 거의 없을 것입니다. 김 씨는 전화번호부의 앞에 표기되어 있을 것이라는 것을 쉽게 알 수 있기 때문입니다.

 

반면 보간 탐색은 찾고자 하는 데이터가 배열의 어디쯤 위치할 것인지를 판단하고 탐색을 수행합니다. 즉, 전화번호부에서 김경수 씨를 찾고자 하면 전화번호부의 앞부분에 있을 것이라고 판단하고 앞부분부터 확인하게 됩니다. 이제 보간 탐색이 어떤 알고리즘을 가지는지 소개하겠습니다.

 

보간 탐색 알고리즘의 경우 한 가지 가정이 필요합니다.

 

"데이터는 정렬되어 있으며 데이터와 인덱스의 관계가 선형적으로 비례한다." 

 

이 말이 무슨 말이냐, 배열에 데이터들이 정렬되어 있을 때, 배열의 인덱스와 데이터의 관계가 다음 그래프와 같이 선형적인 관계를 이루어야 한다는 말입니다.

위와 같이 그래프가 주어질 때 다음과 같은 비례관계를 이용해서 찾고자 하는 데이터의 위치를 알아내게 됩니다.

다음과 같은 배열이 있을 때,

0	1	2	3	4	5	6	7	8	9
1	3	5	7	9	11	13	15	17	19

가장 왼쪽의 인덱스를 low, 가장 오른쪽의 인덱스를 high라고 하고, 찾고자 하는 데이터의 인덱스를 s라고 하겠습니다. 그럼 다음의 비례식을 통해서 s를 구할 수 있습니다.

여기서 arr [s]는 찾고자 하는 데이터 이므로 이를 data라고 이름을 바꾸고 s에 대해서 수식을 정리하면 다음과 같습니다.

이로써 찾고자 하는 data의 위치 s를 구하는 수식이 완성되었습니다. 이 식은 단순하지만 나눗셈 연산이 들어간다는 사실에 주목해야 합니다. 특히 오차율을 줄이기 위해 정수형 나눗셈이 아닌 실수형 나눗셈을 진행한다는 사실에 더 주목할 필요가 있습니다. 왜냐하면 이는 보간 탐색의 단점이기 때문입니다.

 

위 수식을 이용해서 위의 배열에서 7을 찾아보면 s는 3.5로 계산이 됩니다. s는 정수형이므로 이를 내림하면 3이 되고 데이터 7을 찾을 수 있게 됩니다. 만약 해당 인덱스에 찾고자 하는 데이터가 없으면 찾고자 하는 데이터와 해당 인덱스의 값을 비교하고, 탐색 범위를 새로 조정합니다.

---

보간 탐색의 구현에 앞서 하나 기억해야 할 것이 있습니다. 우선은 아래에 정의된 구조체를 보겠습니다.

typedef int Key;
typedef double Data;

typedef struct item
{
	Key searchKey;      //탐색 키
	Data searchData;    //탐색 데이터
}Item;

위에 정의된 구조체 Item의 멤버는 '탐색 키'와 '탐색 데이터'로 구성되어 있습니다.  일반적으로 구리가 자료구조를 공부하는 동안에는 다음 문장이 말하는 방식으로의 탐색이 진행된다고 생각하기 쉽습니다.

 

"다음 배열에서 숫자 3을 찾아야지"

 

하지만 이미 3을 가지고 있으면서 숫자 3을 찾는다는 것은 숫자 3이 배열에 있는지 없는지 확인하는 이상의 의미를 가지지 않습니다. 따라서 다음 문장이 말하는 방식으로의 탐색이 의미 있는 탐색이라고 할 수 있습니다.

 

"사번이 7인 직원의 정보를 찾아야지" 

 

이때 사번이 '탐색 키'가 되고, 직원의 정보가 '탐색 데이터'가 됩니다. 때문에 일반적인 상황에서는 위의 구조체 정의에서 보이듯이 탐색 키와 탐색 데이터를 묶는 형태의 구조체를 정의하게 되고, 앞서 보인 정렬이나 지금 이야기하는 탐색이나, 그 탐색의 대상을 탐색 키에 맞추게 됩니다.

 

그리고 탐색 키는 그 값이 고유해야 합니다. 따라서 같은 키 값을 가지는 데이터는 존재해서는 안 됩니다. 즉, 키에는 그 값이 유일하다는 의미가 담겨 있고, NULL과 같은 값이 채워질 수 없다는 의미도 담겨 있습니다. 

---

이제 앞서 설명한 보간 탐색을 구현해 보겠습니다.

//main.c 소스 파일로 저장
#include <stdio.h>

int ISearch(int arr[], int first, int last, int target)
{
	if (first > last)
	{
		return -1;    //탐색의 실패를 알림
	}

	int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

	if (arr[SPoint] == target)
	{
		return SPoint;
	}
	else if (arr[SPoint] < target)
	{
		return ISearch(arr, SPoint + 1, last, target);
	}
	else
	{
		return ISearch(arr, first, SPoint - 1, target);
	}	
}

int main(void)
{
	int arr[] = { 1, 3, 5, 7, 9 };
	int target = 7;
	int idx = ISearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);

	if (idx == -1)
	{
		printf("탐색 실패!\n");
	}
	else
	{
		printf("타겟 저장 인덱스 : %d\n", idx);
	}

	target = 4;
	idx = ISearch(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, target);

	if (idx == -1)
	{
		printf("탐색 실패!\n");
	}
	else
	{
		printf("타겟 저장 인덱스 : %d\n", idx);
	}

	return 0;
}

/*
실행결과

타겟 저장 인덱스 : 3
탐색 실패!

*/

실행결과를 보면 보간 탐색 알고리즘이 올바르게 구현된 것으로 보입니다. 하지만 위 코드는 두 가지의 문제점을 가지고 있습니다. 첫 번째 문제는 target이 배열의 데이터 범위를 크게 벗어나면 잘못된 참조를 수행한다는 것입니다.

 

위의 코드의 배열에는 1부터 최대 9까지의 데이터가 저장되어 있습니다. 따라서 해당 배열에서 200을 찾는다면 더 볼 것도 없이 당연히 해당 데이터를 찾을 수 없습니다. 그런데 200을 찾기 위해 보간 탐색 알고리즘을 적용하면 어떻게 될까요?

int ISearch(int arr[], int first, int last, int target)
{
	if (first > last)
	{
		return -1;    //탐색의 실패를 알림
	}

	int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

	if (arr[SPoint] == target)
	{
		return SPoint;
	}
	else if (arr[SPoint] < target)
	{
		return ISearch(arr, SPoint + 1, last, target);
	}
	else
	{
		return ISearch(arr, first, SPoint - 1, target);
	}	
}

target이 200이고, first가 0, last가 4일 때, SPoint는 99가 됩니다. 그리고 다음 문장을 보면 배열 arr의 99번지를 참조하고 있음을 볼 수 있습니다. 배열 arr은 그 크기가 5이므로 최대 번지수는 4가 됩니다. 따라서 arr [99]는 배열의 범위를 한참 벗어난 잘못된 참조입니다. 해당 번지수에는 어떤 값인지 모를 쓰레기 값이 포함되어 있고, 정말 운이 나쁘게도 해당 메모리 공간에 200이 저장되어 있으면 ISearch 함수는 200을 찾았다고 99번지를 반환할지도 모릅니다.

 

따라서 우리는 위 함수의 종료 조건을 다음과 같이 수정해야 합니다.

int ISearch(int arr[], int first, int last, int target)
{
	if (target < arr[first] || target > arr[last])
	{
		return -1;    //탐색의 실패를 알림
	}

	int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

	if (arr[SPoint] == target)
	{
		return SPoint;
	}
	else if (arr[SPoint] < target)
	{
		return ISearch(arr, SPoint + 1, last, target);
	}
	else
	{
		return ISearch(arr, first, SPoint - 1, target);
	}	
}

target을 배열의 첫 요소와 마지막 요소의 값과 비교해서 해당 범위를 벗어나면 탐색을 종료합니다.

 

이로써 문제 하나를 해결했습니다. 그런데 종료 조건을 위와 같이 바꿈으로써 두 번째 문제도 해결하게 되었습니다. 두 번째 문제는 함수가 재귀 호출되면서 first와 last가 같아질 때 발생합니다. SPoint는 다음의 수식으로 계산됩니다.

int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

근데 여기서 first와 last가 서로 같다면 arr [last]와 arr [first]도 같아지기 때문에 나눗셈에서 분모가 0이 돼버리는 문제가 발생합니다. 이는 ISearch 함수를 실행하면서 찾고자 하는 값이 하필 배열의 마지막 값과 마지막 전 값의 사이에 해당될 때 발생합니다.

즉, 다음과 같은 배열이 주어져 있을 때,

int arr[] = { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91, 101};

찾고자 하는 값이 92 이상 100 이하라면 함수가 제기능을 하지 못하고 강제 종료됩니다. 물론 앞서 종료 조건을 바꾼 경우에는 문제없이 함수가 실행됩니다. 이 오류를 확인하고 싶으면 다음과 같이 종료 조건을 SPoint를 구하는 수식 밑으로 옮기면 확인이 가능합니다.

int ISearch(int arr[], int first, int last, int target)
{
	int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

	if (target < arr[first] || target > arr[last])
	{
		return -1;    //탐색의 실패를 알림
	}

	if (arr[SPoint] == target)
	{
		return SPoint;
	}
	else if (arr[SPoint] < target)
	{
		return ISearch(arr, SPoint + 1, last, target);
	}
	else
	{
		return ISearch(arr, first, SPoint - 1, target);
	}	
}

종료 조건을 다음과 같이 배치시킴으로써,

int ISearch(int arr[], int first, int last, int target)
{
	if (target < arr[first] || target > arr[last])
	{
		return -1;    //탐색의 실패를 알림
	}

	int SPoint = (double)((target - arr[first]) * (last - first) / (arr[last] - arr[first])) + first;

	if (arr[SPoint] == target)
	{
		return SPoint;
	}
	else if (arr[SPoint] < target)
	{
		return ISearch(arr, SPoint + 1, last, target);
	}
	else
	{
		return ISearch(arr, first, SPoint - 1, target);
	}	
}

이런 문제를 해결할 수 있는 이유는 다음과 같습니다.

first와 last가 같다는 것은 탐색 대상 데이터의 개수가 하나밖에 남지 않았다는 것을 의미합니다. 그런데 다음과 같은 종료 조건은,

if (target < arr[first] || target > arr[last])
{
	return -1;    //탐색의 실패를 알림
}

마지막 남은 데이터와 target이 같지 않으면 탐색에 실패함을 알리고 탐색을 종료하게 합니다. 만약 마지막 남은 데이터와 target이 같았다면, first와 last가 같아지기 전부터 해당 데이터를 찾았을 것입니다.