//first and last occurence in a sorted array
#include
using namespace std;
int first_occurence(int a[],int n,int key)
{
int s=0;
int e=n-1;
int ans=-1;
while(s<=e)
{
int mid=(s+e)/2;
if(a[mid]==key)
{
ans=mid;
e=mid-1;
}
else if(a[mid>key])
e=mid-1;
else
s=mid+1;
}
return ans;
}
int last_occurence(int a[],int n,int key)
{
int s=0;
int e=n-1;
int ans=-1;
while(s<=e)
{
int mid=(s+e)/2;
if(a[mid]==key)
{
ans=mid;
s=mid+1;
}
else if(a[mid>key])
e=mid-1;
else
s=mid+1;
}
return ans;
}
int main()
{
int arr[] = {2, 5, 5, 5, 6, 6, 8, 9, 9, 9};
int n=sizeof(arr)/sizeof(int);
int key;
cin>>key;
cout<<first_occurence(arr,n,key)<<endl;
cout<<last_occurence(arr,n,key);
return 0;
}
In my code,I did the same as coded in the lecture but this is not showing right result for all the test cases.For eg-for input 8 and 9 it is showing -1 hut this numbers are already present over there.
