Saturday, 2 August 2014

First and last occurence of element

/*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();
}

Output:



No comments:

Post a Comment