#include <stdio.h>
#include <conio.h>
int fib(int n); // return a Fibonacci Number
int fibsearch(int a[],int key,int mid ,int p ,int q); //Fibonacci search function
int binsearch(int a[],int i ,int j,int key);/*Recursive binary search*/
int linsearch(int a[],int n , int key);
void main()
{
int a[30],key,mid,p,q,k,n,i,result,op;
clrscr();
do
{
printf("\n1)Linear Search\n2)Binary Search\n3)Fibonacci Search");
printf("\n4)Quit");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
{
case 1: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=linsearch(a,n,key);
if(result==-1)
printf("\n Not found : ");
else
printf("\n Found at location= %d",result);
break;
case 2: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=binsearch(a,0,n-1,key);
if(result==-1)
printf("\n Not found : ");
else
printf("\n Found at location= %d",result);
break;
case 3: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
//locate the kth term of Fibonacci series , such that fib(k) > n
for(k=1 ; fib(k) <= n ; k++)
;
p=fib(k-2);
q=fib(k-3);
mid=n-p+1;
result=fibsearch(a,key,mid,p,q);
if(result==-1)
printf("\n Not found : ");
else
printf("\n Found at location= %d",result);
break;
}
}while(op!=4);
}
int fib(int n)
{ if(n==0) return(0);
if(n==1) return(1);
return(fib(n-1)+fib(n-2));
}
int fibsearch(int a[],int key,int mid ,int p ,int q)
{
int temp;
if(key==a[mid])
return(mid);
if(key> a[mid])
{
if(p==1)
return(-1);
mid=mid+q; // new mid
p=p-q; //p=fib(k-4)
q=q-p; //q=fib(k-5)
return(fibsearch(a,key,mid,p,q));
}
else //key < a[mid]
{
if(q==0)
return(-1);
mid=mid-q; // new mid
temp=p-q;
p=q; //p=fib(k-3)
q=temp; //q=fib(k-4)
return(fibsearch(a,key,mid,p,q));
}
}
int binsearch(int a[],int i, int j,int key)
{
int c;
if(i>j)
return(-1);
c=(i+j)/2;
if(key==a[c])
return(c);
if(key>a[c])
return(binsearch(a,c+1,j,key));
return(binsearch(a,i,c-1,key));
}
int linsearch(int a[],int n , int key)
{
int i;
for(i=0;i<n;i++)
{
if(a[i]==key)
return(i);
}
return(-1);
}
OUTPUT:-
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1
Enter No. of elements : 4
Enter a list of 4 elements : 23 34 8 96
Enter the the element to be searched : 8
Found at location= 2
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1
Enter No. of elements : 3
Enter a list of 3 elements : 12 34 3
Enter the the element to be searched : 12
Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2
Enter No. of elements : 4
Enter a sorted list of 4 elements : 4 8 27 90
Enter the the element to be searched : 5
Not found :
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2
Enter No. of elements : 3
Enter a sorted list of 3 elements : 5 6 89
Enter the the element to be searched : 5
Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 3
Enter No. of elements : 4
Enter a sorted list of 4 elements : 2 13 34 78
Enter the the element to be searched : 13
Found at location= 1
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 4
These blogs are valuable because these are providing such informative information for all the people.
ReplyDeletec++ programming