정의
여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. 탐색 기능을 향상하고자 한다면 이진 탐색 트리 보다 진보된 방법으로 자료를 저장하고 탐색해야 한다.
탐색의 단위는 항목이다. 항목은 가장 간단하게 숫자일 수 있고, 복잡하게는 구조체가 될 수도 있다. 항목 안에는 항목들을 구별시켜주는 키(key)가 존재한다. 이를 탐색키라 하고, 탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것이다.
정렬되지 않은 배열에서의 탐색
순차 탐색
탐색 방법 중 가장 간단하고 직접적인 탐색 방법으로 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법이다.
순차 탐색 코드
int seqSearch(int key,int low, int high){
int i;
for(i = low;i <= high ; i++){
if(list[i] == key)
return i;
}
return -1;
}개선된 순차 탐색
순차 탐색에서 반복문을 보면 키 값의 비교 연산이 있다. 이 비교 연산을 줄이기 위해 리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하도록 설정한 것이 개선된 순차 탐색이다. 성공할 경우 해당 위치를 가리키고 실패했을 경우 -1을 반환한다.
개선된 순차 탐색 코드
int seqSearch2(int key,int low, int high){
int i;
list[high+1] = key;
for(i = low; list[i] != key ; i++) ;
if(i == (high + 1)) return -1;
else return i;
}결론 : 두개의 탐색방법이 뭐가 다른지는 확실히 모르겠음...
정렬된 배열에서의 탐색
이진 탐색
배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내서 탐색의 범위를 반으로 줄인다. 이 방법을 찾고자 하는 key를 찾을 때까지 반복 수행한다. 이 방법은 배열이 미리 정렬되어 있어야 하므로 데이터를 삽입, 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터들에 대한 탐색에 적합하다.
코드(순환 호출 버전)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENTS 10
int list[MAX_ELEMENTS];
int count; // 수행횟수
int binSearch(int list[], int n, int searchNum)
{
int left = 0;
int right = n - 1;
int middle;
count = 0;
while (left <= right) { // 아직 숫자들이 남아 있으면
count++;
middle = (left + right) / 2;
if (searchNum == list[middle]) {
return middle;
}
else if (searchNum < list[middle]) {
right = middle - 1;
}
else {
left = middle + 1;
}
}
return -1; // 발견되지 않음
}
int main()
{
int i;
int search_number;
int return_value;
for (i = 0; i < MAX_ELEMENTS; i++)
list[i] = i;
printf("숫자를 입력하시요.\n");
scanf("%d", &search_number);
return_value = binSearch(list, MAX_ELEMENTS, search_number); // 이진탐색
printf("return value=%d\n", return_value);
printf("문자의 수행횟수=%d\n ", count);
return 0;
}
정렬된 배열에서의 색인 순차 탐색
인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 자료 리스트의 각 n/m번째 데이터를 가지고 있다. 이때 자료 리스트, 인덱스 항목은 모두 정렬되어 있어야 한다.
우선 인덱스 테이블에서 index[i] 〈= key 〈 index[i+1] 을 만족하는 항목을 찾는다. 이 조건을 만족하는 항목으로부터 자료 리스트에서 순차 탐색을 수행한다. 이걸로 탐색 시간을 상당히 줄일 수 있으므로 빠른 시간 안에 원하는 항목을 발견할 수 있게 해주므르 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용한다.
코드
#include <stdio.h>
#define MAX_SIZE 9
#define INDEX_SIZE 3
int list[MAX_SIZE] = { 3, 9,15, 22, 31, 55, 67, 88, 91 };
int n = MAX_SIZE;
typedef struct {
int key;
int index;
} itable;
itable indexList[INDEX_SIZE] = { {3,0}, {22,3}, {67,6} };
int seqSearch(int key, int low, int high)
{
int i;
for (i = low; i <= high; i++)
if (list[i] == key)
return i; /* 탐색에 성공하면 키 값의 인덱스 반환 */
return -1; /* 탐색에 실패하면 -1 반환 */
}
/* INDEX_SIZE는 인덱스 테이블의 크기,n은 전체 데이터의 수 */
int indexSearch(int key) // key : 31
{
int i, low, high;
/* 키 값이 리스트 범위 내의 값이 아니면 탐색 종료 */
if (key<list[0] || key>list[n - 1])
return -1;
/* 인덱스 테이블을 조사하여 해당키의 구간 결정 */
for (i = 0; i < INDEX_SIZE - 1; i++) {
if (indexList[i].key <= key &&
indexList[i + 1].key > key)
break; // key값과 가장 비슷한 값이 있는 index번호를 찾는다.
}
if (i == INDEX_SIZE - 1) { /* 인덱스테이블의 끝이면 */
low = indexList[i].index;
high = n - 1;
}
else {
low = indexList[i].index;
high = indexList[i + 1].index - 1;
}
/* 예상되는 범위만 순차 탐색 */
return seqSearch(key, low, high);
}
//
void main()
{
int i;
i = indexSearch(31);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
for (int j = 0;j < 3;j++) {
printf("%d %d\n", indexList[j].index, indexList[j].key);
}
}
보간 탐색
사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법. 예로 사전을 찾을 때 'ㅎ'으로 시작하는 단어는 사전의 뒷부분에서 찾고 'ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 비슷하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.
Ex) (3, 9, 15, 22, 31, 55, 67, 88, 89, 91)로 구성된 리스트에서 탐색 구간이 0 ~ 9 이고, 찾을 키 값을 55라고 해보자.
탐색 위치 = (55 - 3) / (91 - 3) * (9-0) + 0 = 5.31 ≒ 5
코드
#include <stdio.h>
#define MAX_SIZE 1000
int list[MAX_SIZE];
initList()
{
int i;
for (i = 0;i < 1000;i++)
list[i] = 7 * i;
}
int searchInterpolation(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); //found(r[low])
else return -1; // notfound(key)
}
//
void main()
{
int i = 0;
initList();
i = searchInterpolation(49,1000);
if (i >= 0) {
printf("탐색 성공 i=%d\n", i);
}
else {
printf("탐색 실패\n");
}
}
한성공대생