[알고리즘] 탐색

탐색

; 컴퓨터 기억공간에 저장되어 있는 데이터들로부터 필요한 데이터를 찾아내느 ㄴ것

- 순서화되지 않은 레코드를 탐색하는 방법 ; 순차 탐색, 선형 탐색

 

선형 탐색(linear search)

; 순서대로 인덱스 사용하여 탐색

 

 

이진 탐색(binary search)

; 키 값에 따라 두 부분으로 나누어지고 찾고자 하는 키와 중앙 부분의 키를 비교하여 같으면 탐색 종료, 두 부분 중 크기에 따라 한 쪽 부분을 선택하고 .. 반복

- 탐색 효율이 가장 좋은 방법

#include <iostream>
using namespace std;

#define MAX 5
int arr[5]={10,20,30,40,50};
main(){
    int l=0,h=MAX-1,m,data;
    scanf("%d",&data);
    while(1){
    	m=(l+h)/2;
    	if(arr[m]==data) {
    		cout<<m;
    		break;
		}
    	if(l>h){
    		cout<<"not found";
    		break;
		}
    	else if(arr[m]<data) l=m+1;
		else h=m-1;
    }
    return 0;
}

 

 

피보나치 탐색(Fibonacci Search)

- 피보나치수열의 값을 index로 하여 탐색을 수행하며, 데이터의 범위(개수)보다 하나 더 큰 피보나치 수열의 값을 Fk로 정의하고, 피보나치 수열의 Fk-1,Fk-2,Fk-3을 정의

- Fk-1=i / Fk-2=p / Fk-3=q

- 찾고자 하는 데이터가 i의 값보다 크면 i+=q, p-=q, q-=p

- 찾고자 하는 데이터가 i의 값보다 작으면 i-=q, t=p, p=q, q-=p

- i=0이라면 q==0 , i>=개수라면 i=개수-1

ㅇ

 

보간 탐색(interpolation search)

; 데이터가 있을 만한 위치를 찾아 이동한 후 키 값이 어느 위치에 존재하는가를 추론하여 탐색하는 방법

ki=(k-kl)/(kh-ki) * n = (검색하고자 하는 값 - 가장 작은 값) / (가장 큰 값 - 가장 작은 값) * 레코드 수

n ; 검색하고자 하는 레코드의 수 / k ; 검색하고자 하는 키 값

kl ; n개의 자료들 중에서 가장 작은 키 값 / kh ; n개의 자료들 중에서 가장 큰 키 값

-> ki의 값보다 검색하고자 하는 값이 작다면, 작은 범위로 다시 실행

- 데이터 크기가 클수록 좋은 효율

 

 

블록탐색(block search)

 ; 파일이 몇 개의 블록 단위로 나뉘고, 각 블록 내에는 레코드들이 순차적으로 저장될 필요는 없으나 블록과 블록 사이에는 순차적인 구조로 저장

- 저장된 블록 단위의 리스트는 찾고자하는 데이터가 어느 블록에 있는가 판단한 다음 그 블록 내의 레코드를 순차 탐색에 의해 찾음