Posts Tagged BINARY SEARCH
Program of Binary Search in C, using Recursive and Non Recursive functions.
Posted by admin in C Examples on August 8th, 2009
#include <stdio.h>
#define MAX_LEN 10
/* Non-Recursive function*/
void b_search_nonrecursive(int l[],int num,int ele)
{
int l1,i,j, flag = 0;
l1 = 0;
i = num-1;
while(l1 <= i)
{
j = (l1+i)/2;
if( l[j] == ele)
{
printf("\nThe element %d is present at position %d in list\n",ele,j);
flag =1;
break;
}
else
if(l[j] < ele)
l1 = j+1;
else
i = j-1;
}
if( flag == 0)
printf("\nThe element %d is not present in the list\n",ele);
}
/* Recursive function*/
int b_search_recursive(int l[],int arrayStart,int arrayEnd,int a)
{
int m,pos;
if (arrayStart<=arrayEnd)
{
m=(arrayStart+arrayEnd)/2;
if (l[m]==a)
return m;
else if (a<l[m])
return b_search_recursive(l,arrayStart,m-1,a);
else
return b_search_recursive(l,m+1,arrayEnd,a);
}
return -1;
}
void read_list(int l[],int n)
{
int i;
printf("\nEnter the elements:\n");
for(i=0;i<n;i++)
scanf("%d",&l[i]);
}
void print_list(int l[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d\t",l[i]);
}
/*main function*/
void main()
{
int l[MAX_LEN], num, ele,f,l1,a;
int ch,pos;
clrscr();
printf("======================================================");
printf("\n\t\t\tMENU");
printf("\n=====================================================");
printf("\n[1] Binary Search using Recursion method");
printf("\n[2] Binary Search using Non-Recursion method");
printf("\n\nEnter your Choice:");
scanf("%d",&ch);
if(ch<=2 & ch>0)
{
printf("\nEnter the number of elements : ");
scanf("%d",&num);
read_list(l,num);
printf("\nElements present in the list are:\n\n");
print_list(l,num);
printf("\n\nEnter the element you want to search:\n\n");
scanf("%d",&ele);
switch(ch)
{
case 1:printf("\nRecursive method:\n");
pos=b_search_recursive(l,0,num,ele);
if(pos==-1)
{
printf("Element is not found");
}
else
{
printf("Element is found at %d position",pos);
}
getch();
break;
case 2:printf("\nNon-Recursive method:\n");
b_search_nonrecursive(l,num,ele);
getch();
break;
}
}
getch();
}
Program for all types of Searching in C.
Posted by admin in C Examples on July 1st, 2009
#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;
}
PROGRAM TO COMPARE VARIOUS SEARCH TECHNIQUES.
Posted by admin in C++ Examples on June 14th, 2009
#include<iostream.h> //HEADER FILES
#include<time.h>
#include<fstream.h>
#include<math.h>
fstream file;
int record[30000],key[20000],valid,found; //TO STORE DATA
long int comp=0,avgcomp;
float avgtime;
void seqsearch() //TO PERFORM SEQUENTIAL SEARCH
{
comp=found=0;
int i,j;
for(i=0;i<valid;i++)
{
for(j=0;j<30000;j++)
{
if(record[j]==key[i])
{
//cout<<"\nfound "<<key[i]<<" at "<<j;
found++;
break;
}
//else
comp++;
}
//if(j==30000)
//cout<<"\n not found**********";
}
}
void binsearch() //TO PERFORM BINARY SEARCH
{
comp=found=0;
int top,mid,bot,i;
for(i=0;i<valid;i++)
{
top=0;
bot=29999;
mid=(bot+top)/2;
//cout<<"\n"<<mid;
while(top<=bot)
{
//cout<<"\n"<<mid;
if(record[mid]==key[i])
{
found++;
comp++;
//cout<<"\nfound"<<key[i]<<" at "<<mid;
break;
}
//else
//{
comp++;
if(record[mid]>key[i])
bot=mid-1;
else
top=mid+1;
mid=(bot+top)/2;
//}
}
}
}
void intersearch() // TO PERFORM INTERPOLATION SEARCH
{
comp=found=0;
int top,mid,bot,i;
for(i=0;i<valid;i++)
{
top=0;
bot=29999;
if(top!=bot)
mid=top+(bot-top)*(key[i]-record[top])/(record[bot]-record[top]);
while(bot-top>0)
{
if(record[mid]==key[i])
{
//cout<<"\nfound"<<key[i];
comp++;
found++;
break;
}
else
{
comp++;
if(top==mid||bot==mid)
{
if(record[mid+1]==key[i])
{
found++;
//cout<<"\nfound"<<key[i];
}
//else
// cout<<"\n notfound*******";
break;
}
if(record[mid]>key[i]&&bot!=mid)
bot=mid;
else if(record[mid]<key[i]&&top!=mid)
top=mid;
if(top!=bot)
mid=top+(bot-top)*(key[i]-record[top])/(record[bot]-record[top]);
}
}
}
}
void robintersearch() //TO PERFORM ROBUST INTERPOLATION SEARCH
{
int top,bot,mid,min,max,position=0,k;
int gap,probe;
comp=found=0;
for(k=0;k<valid;k++)
{
bot=29999;
top=0;
gap=sqrt(bot-top+1);
while(top<bot)
{
probe=top+(bot-top)*((key[k]-record[top])/(record[bot]-record[top]));
max=(probe>(top+gap))?probe:(top+gap);
min=(bot-gap);
mid=(min<max)?min:max;
//cout<<"\n"<<probe<<" "<<mid<<" "<<min<<" "<<max<<" "<<top<<" "<<bot;
//comp=comp+2;
if(mid>bot||mid<top)
{
//cout<<"\n not found!!!!!!!!!!!!!!!!!!!!!!";
//comp++;
break;
}
//comp++;
if(key[k]==record[mid])
{
//cout<<"found "<<key[k]<<" at "<<mid<<endl;
found++;
comp++;
break;
}
if(key[k]==record[mid-1])
{
//cout<<"found "<<key[k]<<" at "<<mid-1<<endl;
found++;
break;
}
if(key[k]==record[mid+1])
{
//cout<<"found "<<key[k]<<" at "<<mid+1<<endl;
found++;
break;
}
if((mid-top)<(bot-mid))
{
comp++;
if(key[k]<record[mid])
{
bot=mid-1;
gap=sqrt(bot-top+1);
}
else
{
top=mid+1;
gap=2*gap;
if(gap>((bot-top)/2))
gap=(bot-top)/2;
} //end of if
}
else
{
comp++;
if(key[k]>record[mid])
{
top=mid+1;
gap=sqrt(bot-top+1);
}
else
{
gap=2*gap;
bot=mid-1;
if(gap>((bot-top)/2))
gap=(bot-top)/2;
} //end of if
} // end of if
}
}
}
void main() //EXECUTION STARTS HERE
{
int i,j,k;
cout<<" \n\n WAIT........................";
file.open("records.txt",ios::in);
for(i=0;i<30000;i++) //READING DATA
file>>record[i];
file.close();
file.open("keys.txt",ios::in);
for(i=0;i<20000;i++) //READING KEYS TO BE SEARCHED
file>>key[i];
file.close();
file.open("sequence.txt",ios::out); //SEQUENTIAL SEARCH
long p,q;
for(k=1;k<=200;k++)
{
valid=100*k;
p=clock();
seqsearch();
q=clock();
avgtime=(float)(q-p)/valid;
avgcomp=comp/valid;
file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
}
file.close();
file.open("binary.txt",ios::out); //BINARY SEARCH
for(k=1;k<=200;k++)
{
valid=100*k;
p=clock();
for(j=0;j<100;j++)
binsearch();
q=clock();
avgtime=(float)(q-p)/valid/100;
avgcomp=comp/valid;
file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
}
file.close();
file.open("inter.txt",ios::out); //INTERPOLATION SEARCH
for(k=1;k<=200;k++)
{
valid=100*k;
p=clock();
for(j=0;j<1000;j++)
intersearch();
q=clock();
avgtime=(float)(q-p)/valid/1000;
avgcomp=comp/valid;
file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
}
file.close();
file.open("robinter.txt",ios::out); //ROBUST INTERPOLATION SEARCH
for(k=1;k<=200;k++)
{
valid=100*k;
p=clock();
for(j=0;j<100;j++)
robintersearch();
q=clock();
avgtime=(float)(q-p)/valid/100;
avgcomp=comp/valid;
file<<avgtime*1000<<"\t"<<avgcomp<<"\n";
}
file.close();
}
-
FeedCount
Recent Comments