자료구조 :: 탐색(1) 정의, 정렬되지 않은 배열에서의 탐색;

# 탐색

탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것이다. 그러나 탐색성능을 향상하고자
한다면 이진 탐색 트리와 같은 보다 진보된 방법으로 자료를 저장하고 탐색해야 한다.
탐색의 단위는 항목이다. 항목은 가장 간단하게는 숫자일 수도 있고 아니면 구조체가 될 수도 있다.
항목안에는 항목과 항목을 구별시켜주는 키(key)가 존재한다. 이를 탐색키(search key)라고 한다.
탐색이란 탐색키와 데이터로 이루어진 여러개의 항목 중에서 원하는 탐색 키를 가지고 있는 항목을 찾는 것이다.


# 정렬되지 않은 배열에서의 탐색

1. 순차 탐색(sequential search)

순차 탐색은 탐색 방법중에서 가장 간단하고 직접적인 탐색 방법이다. 순차탐색은 정렬되지 않은 배열의 항목들을
처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법이다.

2. 개선된 순차 탐색

순차 탐색에서 비교횟수는 줄이는 방법으로 리스트의 끝에 키 값을 저장하고 반복문의 탈출 조건을 키값을 찾을때
까지로 설정한다. 이 방법은 비교연산의 수를 반으로 줄일 수 있으므로 탐색 성능을 향상시킬 수 있다.


[정렬되지 않은 배열에서의 탐색 예제]

Sequential_Search.cpp

#include <stdio.h> 

#define N 10

// 순차탐색
int seq_search1(int *list,int low,int high,int key) 
{ 
int i; 
for(i=low;i<=high;i++) 
    { 
if(list[i]==key) return i; 
    } 
return -1; 
} 

// 경계값을 이용한 개선된 순차탐색
int seq_search2(int *list,int low,int high,int key) 
{ 
int i; 
    list[high+1]=key; // 배열 N+1 만큼의 공간이 필요하다.
for(i=low;list[i]!=key;i++) 
        ; 

if(i==(high+1)) return -1; 
elsereturn i;  
} 

int main() 
{ 
int list[N+1]={9,3,5,2,1,4,7,8,6,10}; 
int key; 

    printf("input key : ");    scanf("%d",&key); 

    printf("seq1 - index number : %d\n",seq_search1(list,0,N-1,key)); 
    printf("seq2 - index number : %d\n",seq_search2(list,0,N-1,key)); 

return0; 
}