피보나치 탐색

소개글

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

목차

이진 탐색과 비슷하여 이미 정렬된 데이터의 집합들로부터 특정한 키를 찾는 방법    피보나치 탐색은 피보나치 수열을 이용하여 다음 탐색 구간을 정함    피보나치 수열 : 1, 1, 2, 3, 5, 13, 21, 34, ...         (단,  )    피보나치 탐색의 과정 : 배열 에 오름차순으로 정렬된 데이터의 개수가 이라 가정  ① 초기화 : ②    만일 이면 ③으로 간다만일 이면 ④로 간다만일 이면 탐색 완료③   만일 이면 는 배열 안에 없다만일 이면 로 정하고 ②로 간다④   만일 이면 는 배열 안에 없다만일 이면 로 정하고 ②로 간다

본문내용

로 수행 속도가 다소 떨어질 수 있음


비교할 키의 위치 계산을 할 때 이진탐색처럼 나눗셈을 사용하지 않고덧셈과 뺄셈을 사용함으로서 평균 검색 효율을 높일 수 있음




피보나치 탐색의 구현



public void fibonacciSearch( int A[ ], int size, int key ) {
int tmp, index, adj, fmin2, fmin3;
tmp = fiNum(size); adj = size - fib(tmp);
index = fib(tmp - 1); fmin2 = fib(tmp - 2); fmin3 = fib(tmp - 3);
if (key > A[index]) index = index + adj;
while (index >= 0 && index < size) {
if (key == A[index]) return(index);
else if (key < A[index]) {
index = index - fmin3; tmp = fmin2;
fmin2 = fmin3; fmin3 = tmp - fmin3; }
else { index=index+fmin3; fmin2=fmin2-fmin3; fmin3=fmin3-fmin2; }
}
return(-1);
}
public void finum (int num) {
int I, p, q, tmp;
if (num == 0) return (0);
if (num == 1) return (1);
p = 0; q = 1;
for (i=1; p+q <= num; I++) { tmp = q; q += p; p = tmp; }
return(i);
}