정보처리산업기사-검색(Search)

검색은 컴퓨터를 이용하여 기억공간에 보관중인 특정 레코드를 찾아내는 작업입니다.

---

선형 검색(Linear Search)

• 선형 검색은 순서화되지 않은 파일에서 순차적으로 검색하는 것으로 키값을 첫번째 레코드 키값부터 차례로 비교함
• 순차 검색(Sequential Search)라고도 합니다.
• 프로그램 작성이 가장 쉽습니다.
• 평균 검색 횟수는 (n+1)/2입니다.

---

제어 검색(Control Search)

• 제어 검색은 반드시 순서화되어있어야 검색할 수 있습니다.
• 한번의 비교 동작이 끝나고 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용해 검색합니다.

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

• 전체 파일을 두개의 서브파일로 분리하며 키 레코드를 검색합니다.
• 찾으려는 키의 값을 파일으 중간 레코드 키값과 비교하면서 검색합니다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어들어 탐색 효율이 좋고 탐색 시간이 적게 소모됩니다.
• 중간 레코드 번호 M = (F+L)/2 (F : 첫번째 레코드,L:마지막 레코드 번호)

피보나치 검색(Fibonacci Search)

• 피보나치 검색은 피보나치 수열에 따라 검색합니다
• 이분 검색에서는 중간 레코드 번호를 계산하기 위해 나눗셈을 하지만 피보나치 검색은 가감산만을 이용하기 때문에 효율이 좋습니다.

보간 검색(Interpolation Search)

• 보간 검색은 찾으려는 레코드가 있음직한 부분의 키를 택하여 검색하는 방식입니다.
• 선정 레코드 번호 = (찾으려는 키값 - 최소 키 값) / (최대키 값- 최소키값) -> 에 * 레코드수를 합니다.
• 실제로는 예측을 해야하니 프로그래밍이 불가합니다.

블록 검색(Block Search)

• 파일을 구성하는 레코드들을 여러개의 블록으로 분할하여 순서화 시키고 블록 내의 자료는 순서화와 상관없이 저장
• Index 부분을 두어, 각 Bolck마다 최대 레코드 키 값을 가지는 레코드 번호를 저장합니다.
• 인덱스를 이용하여 레코드가 어느 블록에 속하는지 검색한두 해당 블록 내에서는 선형 검색을 합니다.

이진 트리 검색(Binary Tree Search)

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