탐색 알고리즘 : 순차 탐색, 이진 탐색, 보간 탐색

탐색

: 여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 키로 항목을 서로 구별. 배열, 연결 리스트, 트리, 그래프, 해시 테이블 등을 사용

 

①  순차 탐색

 

▷ 아이디어

: 처음부터 마지막까지 하나씩 순차적으로 확인

 

8을 탐색하는 경우와 2를 탐색하는 경우의 예시

 

▷ 프로그램

int sequential_search(int key, int low, int high){
    for(int i = low; i<=high; i++){
        if(list[i] == key)
            return i; // 성공 탐색
    return -1; // 실패 탐색
}

 

 

▷ 시간 복잡도

: 실패 탐색을 하는 최악의 경우 총 n번의 비교 연산이 시행되기 때문에 전체적으로 시간 복잡도는 O(n).

 

 

 

 

 

② 이진 탐색

 

▷ 아이디어

: 배열이 정렬되어 있는 경우, 중앙값과 비교하여 왼쪽 혹은 오른쪽 부분 배열로 탐색 범위를 점차 좁혀나간다.

 

34를 탐색하는 경우의 예시

 

▷ 알고리즘

1. 중간 위치를 계산한 후 키값을 중앙값과 비교

2. 중앙값보다 작다면 왼쪽 부분 배열을 기준으로, 크다면 오른쪽 부분 배열을 기준으로 재귀 함수 호출

 

 

 

▷ 프로그램

//재귀 함수
int search_binary(int key, int low, int high){
    if (low > high) return -1;
    
    int middle = (low+high)/2;
    if (key == list[middle]) return middle;
    else if (key < list[middle]) return search_binary(key, low, middle-1);
    else return search_binary(key, middle+1, high);
    
}

//반복 함수
int search_binary2(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]) low = middle+1;
        else high = middle-1;
    }
    return -1;
}

 

 

▷시간 복잡도

: n(=2^k)개의 원소를 가지는 리스트의 경우 logn번의 분할이 시행되므로 시간 복잡도는 O(logn)

 

 

 

 

 

③ 보간 탐색

 

▷ 아이디어

: 이진 탐색과 유사하지만, 사전에서 단어를 찾을 때 'ㄱ'으로 시작하는 단어는 앞부분에서 찾고 'ㅎ'으로 시작하는 단어는 뒷부분에서 찾듯이, 원소들이 일정하게 분포되어 있다고 원소값에 대한 사전 지식을 활용하여 리스트를 불균등하게 분할하여 탐색하는 방법.

 

 

 

▷ 알고리즘

1. 키값을 이용해 키값 k가 있을 기대 위치를 계산

2. 해당 위치의 값과 키값을 비교.

3. 비교값보다 k가 작다면 왼쪽 부분 배열을 기준으로, 크다면 오른쪽 부분 배열을 기준으로 재탐색

 

키값의 기대위치를 구하는 방법

 

▷프로그램

int search_interpolation(int key, int n){
    int low = 0;
    int high = n-1;
    
    while((list[high] >= key) && (key > list[low])){
        int 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; // 실패 탐색

 

 

▷시간 복잡도

: 최악의 경우 O(n), 평균적인 경우에는 O(loglogn)의 시간 복잡도를 가져 테이블이 작은 경우에는 이진 탐색이 효율적이고, 테이블이 큰 경우에는 보간 탐색이 매우 효율적.