Program for all types of Searching in C.

#include<stdio.h>
#include<math.h>
FILE *fp,*fpr;
int i,s[40000],z[40000],a[11];
void func_seque();
void binary();
void interpole();
void ro_interpole();

main()
{
fp=fopen("x.txt","r");
fpr=fopen("y.txt","r");
if(fp==NULL||fpr==NULL)
{
printf("error in opeaning the file\n");
exit(1);
}
for(i=0;i<40000;i++)
{
fscanf(fp,"%d",&s[i]);
fscanf(fpr,"%d",&z[i]);
}
a[0]=0;a[1]=s[99];a[2]=s[199];a[3]=s[499];a[4]=s[999];a[5]=s[1999];a[6]=s[4999];a[7]=s[9999];
a[8]=s[19999];a[9]=s[29999];a[10]=s[39999];

func_seque();
binary();
interpole();
ro_interpole();
}

void func_seque()
{
int i,j,ts[11],t;
printf("\n-----------------------------------------------------------\n");
printf("sequencial search\n");
printf("-----------------------------------------------------------\n");
printf("\tS.no\tvalue\t\tposition\t\ttime\n");
for (i=1;i<11;i++)
{
t=1;
for (j=0;j<40000;j++)
{
if(a[i]==z[j])
{
printf("\t%d\t%d  \t\t%d\t\t%d\n",i,a[i],j+1,t);
ts[i]=t;
break;
}
t++;
}
}
return;
}

void binary()
{
printf("\n-----------------------------------------------------------\n");
printf("binary search\n");
printf("-----------------------------------------------------------\n");
printf("\tS.no\tvalue\t\tposition\t\ttime\n");
int low,high, mid,i,ts[11],t=1;
for(i=1;i<11;i++)
{
low=0;high=39999;t=1;
for (;low<=high;)
{
mid=(low+high)/2;
if(a[i]==z[mid])
{
printf("\t%d\t%d\t\t%d\t\t%d\n",i,a[i],mid+1,t);
ts[i]=t;
break;
}
if( a[i]<z[mid])
high=mid-1;
else
low=mid+1;
t++;
}

}
return;
}

void interpole()
{
printf("\n-----------------------------------------------------------\n");
printf("interpolation search\n");
printf("-----------------------------------------------------------\n");
printf("\tS.no\tvalue\t\tposition\t\ttime\n");
int low,high, mid,i,ts[11],t,band,kband,gap,g,ga;
for(i=1;i<11;i++)
{
low=0;high=39999;t=1;
for (;low<=high;t++)
{
band=z[high]-z[low];
kband=a[i]-z[low];
g=high-low;
ga=g*kband;
gap=(int)(ga/band);
mid=low+gap;
if(a[i]==z[mid])
{
printf("\t%d\t%d\t\t%d\t\t%d\n",i,a[i],mid+1,t);
ts[i]=t;
break;
}
if( a[i]<z[mid])
high=mid-1;
else
low=mid+1;
}

}
return;
}

void ro_interpole()
{
printf("\n-----------------------------------------------------------\n");
printf("robust interpolation search\n");
printf("-----------------------------------------------------------\n");
printf("\tS.no\tvalue\t\tposition\t\ttime\n");

int y,probe,low,high, mid,i,ts[11],t,gap,p,q,r,s,m;
for(i=1;i<11;i++)
{
low=0;high=39999;t=1;
for (;low<=high;)
{
p=z[high]-z[low];
q=a[i]-z[low];
r=high-low;
s=r*q;m=(int)(s/p);
probe=low+m;
gap = (int)(sqrt(high-low+1));
if(gap<=1)
gap=0;
if(probe>=low+gap)
y=probe;
else y=low+gap;
if(high-gap<=y)
mid=high-gap;
else mid=y;
if(a[i]==z[mid])
{
printf("\t%d\t%d\t\t%d\t\t%d\n",i,a[i],mid+1,t);
ts[i]=t;
break;
}
if( a[i]<z[mid])
high=mid-1;
else
low=mid+1;
t++;
}

}
return;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s