피보나치탐색, 보간탐색

소개글

피보나치탐색, 보간탐색에 대한 보고서 자료입니다.

본문내용

file[low].key)
switch(ch = COMPARE (key, s_file[mid].key))
{
case ' <' : high = mid;
break;
case ' = ' : return(mid);
case ' >' : low = mid;
}
}
}

[예제] 다음 13개의 레코드에서 35를 보간 탐색으로 찾아보시오.
인덱스
1
2
3
4
5
6
7
8
9
10
11
12
13
키
1
2
7
13
18
19
21
26
27
29
30
35
40
① k = 35, n = 13, kh = 40, kℓ = 1일 때
i = (35 - 1)/(40 - 1) * 13 = 11이 되어
k = 35, ki = 30 이므로 k >ki 이 되어
찾을 레코드는 인덱스 12에서 13 사이에 있다.
② 인덱스 12부터 선형 탐색으로 탐색하면
k = 35, k12 = 35 이므로 k = k12가 되어 키 35를 가진 레코드를 찾음
보간 검색의 평균 탐색 시간 : O(log2(log2n))
성능은 파일이나 표의 분포에 영향을 받게 되므로 일양 분포(uniformdistribution)에 대 해서 매우 좋다.