/*Program to find first and last occurence of an element and to find number of times it occurs in a sorted array using binary search.*/
#include<iostream.h>
#include<conio.h>
int binary(int a[10],int n,int x,int first_search )
{
int beg=0,end=n-1,mid,result=-1;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==x)
{
result=mid;
if(first_search==1)
end=mid-1;
else
beg=mid+1;
}
else if(a[mid]<x)
beg=mid+1;
else
end=mid-1;
}
return result;
}
void main()
{
clrscr();
int A[10],N,i,s;
cout<<"\nEnter size of array : ";
cin>>N;
cout<<"\nEnter sorted array : ";
for(i=0;i<N;i++)
{
cin>>A[i];
}
cout<<"\nEnter number : ";
cin>>s;
int first_occ=binary(A,N,s,1);
int last_occ=binary(A,N,s,0);
if( first_occ==-1||last_occ==-1)
cout<<"\nNumber does not exist !!";
else
{
cout<<"\nFirst occurence of "<<s<<" is at index "<<first_occ;
cout<<"\n\nLast occurence of "<<s<<" is at index "<<last_occ;
}
getch();
}
#include<iostream.h>
#include<conio.h>
int binary(int a[10],int n,int x,int first_search )
{
int beg=0,end=n-1,mid,result=-1;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==x)
{
result=mid;
if(first_search==1)
end=mid-1;
else
beg=mid+1;
}
else if(a[mid]<x)
beg=mid+1;
else
end=mid-1;
}
return result;
}
void main()
{
clrscr();
int A[10],N,i,s;
cout<<"\nEnter size of array : ";
cin>>N;
cout<<"\nEnter sorted array : ";
for(i=0;i<N;i++)
{
cin>>A[i];
}
cout<<"\nEnter number : ";
cin>>s;
int first_occ=binary(A,N,s,1);
int last_occ=binary(A,N,s,0);
if( first_occ==-1||last_occ==-1)
cout<<"\nNumber does not exist !!";
else
{
cout<<"\nFirst occurence of "<<s<<" is at index "<<first_occ;
cout<<"\n\nLast occurence of "<<s<<" is at index "<<last_occ;
}
getch();
}
Output:
No comments:
Post a Comment