Search.h : 다양한 탐색 함수를 포함함 헤더

• 색인 순차 탐색

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

색인 순차 탐색 알고리즘은 우선 인덱스 테이블에서 index[i] <= key < index[i+1]을 만족하는 항목을 찾는다. 해당하는 항목을 찾으면 주 자료 테이블에서 해당 범위의 항목들에 대해서만 검색하면 된다. 이 방법은 주 자료 리스트에서의 탐색 시간을 상당히 줄일 수 있으므로 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용하는 방법이다. 

색인 순차 탐색 알고리즘의 탐색 성능은 인덱스 테이블의 크기에 좌우된다. 인덱스 테이블의 크기를 줄이면 주자료 리스트에서의 탐색 시가능ㄹ 증가시키고, 인덱스 테이블의 크기를 크게 하면 인덱스 테이블의 탐색 시간을 증가시킨다. 인덱스 테이블의 크기를 m이라 하고 주자료 리스트의 크기를 n이라 하면 색인 순차 탐색의 복잡도는 와 같다. 물론 주자료 리스트의 탐색에서 이진 탐색을 사용할 수도 있다.

• 보간 탐색

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

보간 탐색은 이진 탐색과 같은 의 시간 복잡도를 가지지만 많은 데이터가 비교적 균등하게 분포되어 있는 자료의 경우 훨씬 효율적인 방법이 된다.

---

#pragma once

#ifndef ___Search

#define ___Search

// Search.h : 다양한 탐색 함수를 포함함 헤더

// int 배열 list의 순차탐색

int sequentialSearch(int list[], int key, int low, int high) {

for (int i = low; i <= high; i++)

if (list[i] == key)

return i; // 탐색에 성공하면 키 값의 인덱스 반환

return -1; // 탐색에 실패하면 -1 반환

}

// 오름차순으로 정렬된 배열 list의 순차 탐색

int sortedSequentialSearch(int list[], int key, int low, int high) {

int i;

if (key < list[low] || key>list[high]) return -1;

for (i = low; i <= high; i++) {

if (list[i] > key) return -1;

if (list[i] == key) return i;

}

}

// 재귀호출을 이용한 이진탐색 함수

int binarySearch(int list[], int key, int low, int high) {

int middle;

if (low <= high) { //하나 이상의 항목이 있어야 탐색

middle = (low + high) / 2;

if (key == list[middle]) // 탐색 성공

return middle;

else if (key < list[middle]) // 왼쪽 부분리스트 탐색

return binarySearch(list, key, low, high);

else

return binarySearch(list, key, low, high);

}

return -1; // 탐색 실패

}

// 반복문을 이용한 이진탐색 함수

int binarySearchIter(int list[], int key, int low, int high) {

int middle;

while (low <= high) { // 항목들이 남아 있으면(종료 조건)

middle = (low + high) / 2;

if (key == list[middle]) // 탐색 성공

return middle;

else if (key > list[middle]) // key가 middle의 값보다 크면

low = middle + 1; // middle + 1 ~ high 사이 검색

else                                // key middle 의 값보다 작으면

high = middle - 1; // low ~ middle-1 사이 검색

}

return -1; // 탐색 실패

}

// 인덱스 테이블 항목의 구조체

struct Index {

int key; // 키 값

int index; // 키 값의 인덱스

};

// 색인 순차 탐색 함수

int indexedSearch(int list[], int nList, Index* table, int nTable, int key) {

if (key < list[0] || key>list[nList - 1]) // 키 값이 리스트 범위 밖

return -1;

for (int i = 0; i < nTable - 1; i++) { // 인덱스 테이블 조사

if (table[i].key <= key && table[i + 1].key > key)

return sequentialSearch(list, key,

table[i].index, table[i + 1].index);

}

return sequentialSearch(list, key, table[nTable - 1].index, nList);

}

// 반복문을 이용한 보간 탐색

int interpolationSearch(int list[], int n, int key) {

int low = 0;

int high = n - 1;

while ((list[low] < key) && (key <= list[high])) {

int j=(int)((float)(key-list[low])/(list[high]-list[low])

*(high - low)) + low; // float 형으로 변환하지 않으면 정수로 계산되어 0 이 됨

if (key > list[j]) low = j + 1;

else if (key < list[j]) high = j - 1;

else return j; // 탐색 성공

}

return -1; // 탐색 실패

}

#endif // !___Search