[Algorithm] 여러가지 검색(Search)기법

 여러가지 검색의 종류 

검색이란 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업이다.

 

선형 검색(Linear Search)

1. 선형 검색은 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로 찾고자 하는 Key값을 첫번째 레코드 Key값으로부터 차례로 비교하여 검색하는 방식이다.

2. 순차검색(Sequential Search)라고도 한다.

3. 프로그램 작성이 비교적 간단하다.

 

제어 검색(Control Search)

1. 제어 검색은 반드시 순서화된 파일이어야 검색할 수 있다.

2. 한번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식이다.

 

이분 검색(이진 검색, Binary Search)

1. 이분검색은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식이다.

2. 찾고자 하는 Key값을 파일의 중간 레코드 Key값과 비교하면서 검색하는 방식이다.

3. 비교횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색효율이 좋고 탐색시간이 적게 소요된다.

 

피보나치 검색(Fibonacci Search)

1. 피보나치 검색은 피보나치 수열에 따라 다음에 비교할 대상을 선정하여 검색하는 방식이다.

2. 이분 검색에서는 중간 레코드 번호를 계산하기 위해서 나눗셈이 필요하지만 피보나치 검색은 가감산만을 이용하기 때문에 효율이 우수하다.

 

보간 검색(Interpolation Search)

1. 보간 검색은 찾으려는 레코드가 있음직한 부분의 키를 택하여 검색하는 방식이다.

2. 찾으려는 레코드 근처에서부터 찾아가기 때문에 검색시간이 빠르지만, 예측을 해야하므로 실제로는 프로그래밍이 불가능하다.

 

블록 검색(Block Search)

1. 블록 검색을 위해서는 파일을 구성하는 레코드들을 다음과 같이 구성해 놓아야 한다.

2. 파일을 구성하는 레코드들을 여러개의 Block으로 분할하여 Block단위는 순서화 시키고 Block내의 자료는 순서화와 관계없이 저장시킨다.

3. Index부분을 두어, 각 Block마다 최대 레코드 키 값을 가지는 레코드 번호를 저장시킨다.

4. 인덱스를 이용하여 찾고자 하는 레코드가 어느 Block에 속하는지 검색한 후, 해당 Block내에서는 선형 검색을 한다.

※ 위와 같이 구성되어 있을 때, 39를 검색하기 위해서는 인덱스에서 2, 7, 12가 가리키는 값과 비교하고, 세번째 블록에서 42, 40, 39와 차례로 비교하므로 6번 비교하여 성공한다.

 

 이진 트리 검색(Binary Tree Search) 

이진 트리 검색은 파일을 이진 검색 트리로 구성하여 검색하는 방식이다.

 

검색과정

1. 찾고자 하는 레코드 KEy값 X가 이진 검색 트리에 존재하는지 조사하려면 먼저 Root Node와 비교한다.

2. 만약 X가 Root Node의 Key값보다 작으면 왼쪽 Subtree로 검색을 계속하고, 크면 오른쪽 Subtree로 검색을 계속하고 같으면 검색을 종료한다.

3. i가 0인 경우 검색에 실패한 경우이다. 즉 X가 임의의 노드 값과 같지 않아서 왼쪽 또는 오른쪽 자식을 찾아가기 위해 그 노드의 L.L또는 R.L 포인터를 i에 기억시켰을 때, i에 기억시킨 포인터 값이 Nill Pointer인 경우 찾고자 하는 레코드가 없기 떄문이다.