색인 순차 탐색

색인 순차 탐색이란 인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 주 자료리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m번째 데이터를 가지고 있다. 이 때 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

Untitled

색인 순차 탐색은 위의 그림에서 보듯이 우선 인덱스 테이블에서 index[i] ≤ key < index[i + 1]을 만족하는 항목을 찾는다. 인덱스 테이블에서 위의 조건을 만족하는 항목으로부터 주 자료 리스트에서 순차 탐색을 수행한다. 이 방법은 주 자료 리스트에서의 탐색 시간을 상당히 줄일 수 있으므로 빠른 시간 안에 원하는 항목을 발견할 수 있게 해주므로 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용하는 방법이다.

순차 탐색 알고리즘 코드

//INDEX_SIZE는 인덱스 테이블의 크기, n은 전체 데이터의 수
int search_index(int key, int n){
	int i, low, high;

	//키 값이 리스트 범위 내의 값이 아니면 탐색 종료
	if(key < list[0] || key > list[n - 1]
		return -1

	//인덱스 테이블을 조사항여 해당키의 구간 결정
	for(i = 0; i < INDEX_SIZE; i++)
		if(index_list[].key <= key && index_list{i + 1].key > key)
			break;

	if(i == INDEX_SIZE){ //인덱스 테이블으 끝이면
		low = index_list[i - 1].index;
		high = n;
	}
	else{
		low = index_list.index;
		high = index_list[i + 1].index;
	}

	//예상되는 범위만 순차 탐색
	return seq_search(key, low, high);

}

main() 함수는 키 값을 매개변수로 사용하여 search_index 함수를 호출하며, 탐색이 성공하면 search_index 함수는 해당키의 인덱스를 반환한다.

색인 순차 알고리즘의 성능

색인 순차 탐색 알고리즘의 탐색 성능은 인덱스 테이블의 크기에 좌우된다. 인덱스 테이블의 크기를 줄이면 주 자료 리스트에서의 탐색 시간을 증가시키고, 인덱스 테이블의 크기를 크게 하면 인덱스 테이블의 탐색 시간을 증가시킨다. 인덱스 테이블의 크기를 m이라 하고 주 자료 리스트의 크기를 n이라 하면 색인 순차 탐색의 복잡도는 O(m+n/m)와 같다.

보간 탐색

보간 탐색은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법이다. 이는 우리가 사전을 찾을 떄 ‘ㅎ’으로 시작하는 단어는 사전의 뒷부분에서 찾고 ‘ㄱ’으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.

Untitled

이진 탐색에서 탐색 위치는 항상 (low + high) / 2 이나. 보간 탐색에서는 찾고자하는 키 값과 현재의 low, high 위치의 값을 고려하여 위의 그림과 같이 탐색 위치를 결정한다.

여기에서 k는 찾고자 하는 키 값을, low과 high는 각각 탐색할 범위의 최소, 최대 인덱스 값을 나타낸다. 즉, 위의 식은 탐색 위치를 결정할 떄 찾고자 하는 키 값이 있는 곳에 근접하게 되도록 가중치를 주는 것이다.

보간 탐색의 코드

int interpol_search(int key, int n) { 
	int low, high, j;
	low = 0; 
	high = n - 1;

	while ((list[high] >= key) && (key > list[low])) {
	j = ((float)(key - list[low]) / (list[high] - list[low]) * (high - low)) + low; 
	if (key > list[j]) 
		low = j + 1;
	else if (key < list[j]) 
		high = j - 1;
	else 
		low = j;
	}

if (list[low] == key) 
	return(low); // 탐색성공
else 
	return -1; // 탐색실패 
}