자료구조 :: 탐색(2) 정렬된 배열에서의 탐색

# 정렬된 배열에서의 탐색

1. 제어 탐색(control search)

제어 탐색은 배열의 중앙 값을 기준으로 키값보다 작다면 작은 부분, 크다면 큰 부분 배열을 탐색하는 방법이다.


2. 이진 탐색(binary search)

정렬된 배열의 탐색에는 이진 탐색이 가장 적합하다. 이진 탐색은 제어 탐색보다 발전된 방법으로 탐색의 범위를
계속적으로 탐색할 리스트의 크기를 반으로 줄인다.


3. 보간 탐색(interpolation search)

보간 탐색은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색 키가 존재할 위치를 예측하여 탐색하는 방법이다.
보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.
보간 탐색의 인덱스를 구하는 방법은 다음과 같다.

탐색 인덱스 i = (k - list[low]) / (list[high] - list[low]) * (high - low) + low

일반적으로 계산되어 나오는 값은 실수이며 항상 정수로 변환하여 주어야 한다. 많은 데이터가 비교적 균등하게
분포되어 있을 경우 보간 탐색은 이진 탐색보다 우수한 방법이 될 수 있으며 보간 탐색 알고리즘은 이진 탐색과
비슷한 O(log₂n)의 복잡도를 가진다.

[정렬된 배열에서의 탐색 예제] , 정렬은 퀵정렬을 사용

Sort_Array_Search.cpp

#include <stdio.h> 
#include<stdlib.h> 
#include<time.h> 

#define N 15
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) 

// 제어 탐색
int control_search(int *list,int low,int high,int key) 
{ 
int mid=(low+high)/2; 
int i; 

if(key == list[mid]) 
return mid; 
elseif(key < list[mid]) 
        high=mid; 
else
        low=mid; 

for(i=low;i<=high;i++) 
    { 
if(list[i]==key) 
return i; 
    } 

return -1; 
} 

// 이진 탐색
int binary_search(int *list,int low,int high,int key) 
{ 
int mid; 

while(low<=high) 
    { 
        mid=(low+high)/2; 

if(key == list[mid]) 
return mid; 
elseif(key < list[mid]) 
            high=mid-1; 
else
            low=mid+1; 
    } 

return -1; 
} 

// 보간 탐색
int interpolation_search(int *list,int low,int high,int key) 
{ 
int i; 

while((list[high] >= key) && (key > list[low])) 
    { 
         i=(key-list[low])/(list[high]-list[low])*(high-low)+low;  

if(key == list[i]) 
return i; 
elseif(key < list[i]) 
            high=i-1; 
else
            low=i+1; 
    } 

if(list[low]==key) return low; 
elsereturn -1; 
} 

void QuickSort(int *list, int left, int right) 
{ 
int i,j,pivot,temp; 

if(left<right) 
    { 
        i=left; 
        j=right+1; 

        pivot=list[left]; // pivot은 리스트의 첫번째 값

do{ 
while(list[++i] < pivot); // left부터 pivot값보다 작은값을 찾는다
while(list[--j] > pivot); // right부터 pivot값보다 작은값을 찾는다

if(i < j) 
                SWAP(list[i],list[j],temp); // 검색한 인덱스끼리 교환
        }while(i < j); 

        SWAP(list[left],list[j],temp); // pivot의 자리를 변경

// pivot을 기준으로 반으로 나누고 각각을 재귀 호출로 반복 정렬 한다
        QuickSort(list,left,j-1);  
        QuickSort(list,j+1,right);         
    } 
} 

int main() 
{ 
int key,i; 
int *list=(int*)malloc(sizeof(int)*N); 

    srand(time(NULL)); 

for(i=0;i<N;i++) 
        list[i]=rand()%1000; 

    QuickSort(list,0,N-1); 

for(i=0;i<N;i++) 
        printf("index %d : %d\n",i,list[i]); 

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

    printf("control_search - index number : %d\n",control_search(list,0,N-1,key)); 
    printf("binary_search - index number : %d\n",binary_search(list,0,N-1,key)); 
    printf("inte_search - index number : %d\n",interpolation_search(list,0,N-1,key)); 


return0; 
}