피보나치 탐색 , 보간탐색

소개글

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

본문내용

High로, S보다 작다면 k값을 Low로 변경하고 다시 같은 방법으로 탐색을 하게된다. 보간 탐색의 경우 이진 탐색과 마찬가지로 재귀적인 방법으로 탐색을 하게되지만, 키가 대충 어디쯤에 있을 것이라는 추정 범위가 좀 더 정확하기 때문에 평균적으로 이진탐색보다 효율적인 방법이라 할 수 있다. 실제로 테스트 해 본 결과 평균적으로 이진 탐색보다 더 적은 비교횟수로 데이터를 찾는 것을 확인 할 수 있었다.아래는 보간 탐색의 소스 코드이다. 데이터를 정렬하기 위해 Quick Sort를 사용하였으며 Quick Sort에 대해서는 이후에 포스팅 할 계획이다.
보간 탐색(interpolation search) **=================================**/#include#define MAX 20 /*데이터의 최대수를 의미하는 매크로*/int interpolation_search(int a[],int x, int n);void quick(int a[], int left, int right);void main(){int i,n,key,pos;int a[MAX];printf(\"Number of data => \");scanf(\"%d\",&n);for(i=0; i /*표준 입력 장치를 통해 데이터를 입력*/printf(\"%i\\\'s number=> \", i+1);scanf(\"%d\",&a[i]);}printf(\"\\nInput data: \");for(i=0; i printf(\"%d \",a[i]);}int k;quick(a,0,n-1);printf(\"\\nAfter quick_sort: \");for(k=0; kprintf(\"%d \",a[k]);printf(\"\\n\");printf(\"\\nSearch data => \");scanf(\"%d\", &key);/* interpolation_search함수 호출 */pos=interpolation_search(a,key,n);if(pos !=-1)printf(\"array[%d] : %d\\n\",pos+1,a[pos]);elseprintf(\"Not found : %d\\n\",key);}int interpolation_search(int a[],int x, int n){int low,high,mid;low=0; high=n-1;while(low<=high){/* 중간에 있는 데이터 인덱스 계산 */mid=low+(high-low)*(x-a[low])/(a[high]-a[low]);if(x high=mid-1;else if(x==a[mid])return mid;else low=mid+1;}return -1;}void quick(int a[], int left, int right){ /*퀵정렬 알고리즘*/int s,t,i,j;if(lefts=a[(left+right)/2];i=left-1; j=right+1;while(1){while(a[++i]while(a[--j]>s);if(i>=j) break;t=a[i]; a[i]=a[j]; a[j]=t;}quick(a,left,i-1);quick(a,j+1,right);}}