First and last occurrences of element

a sorted array is given may contain duplicate elements we should find the first and last occurance of an element k if not found return -1

Input: 
n = 9 
k = 5
Arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}
Output: 2 5
Explanation: first Arr[2] = 5 and last Arr[5] = 5

method 1:Naive Approach 

1)iterate or run through whole array
2)to find first occurance in sorted array a[i] should be equal to k(the element we are searching)
but a[i-1] is not equal to k
3) to find last occurance in sorted array a[i] should be equal to k(the element we are searching)
but a[i+1] is not equal to k
4) lets take a variable c and lets makes its value 0 , n its value is increased if the element k is found
else we will return -1

you can use the above algorithm to code in any language:

implementation in c++:

void FirstLastOccur(int n, int k ,int a[])
{           int c=0;
	   for(int i=0;i<n;i++)
	   {
	       if((a[i]==k && a[i-1]!=k ))
	       {
	       cout<<i<<" ";
	        c++;
	       }
	       if( a[i]==k &&a[i+1]!=k )
	       {
	       cout<<i<<" ";
	        c++;
	       }
	   }
	   
	   if(c==0)
	   cout<<-1<<" ";
	   cout <<endl;
	    
}

Time Complexity: O(n)
Auxiliary Space: O(1)

method 2:Efficient solution

use binary search:

1)find mid =(low+high)/2

2)to find first occurance in sorted array arr[mid] should be equal to k(the element we are searching)
but arr[mid-1] is not equal to k than we should return mid
elseif  k is greater than arr[mid] we should call the function recursively on the right half
else  k is smaller than arr[mid] we should call the function recursively on the left half
if element is not found return -1

3)to find last occurance in sorted array arr[mid] should be equal to k(the element we are searching)
but arr[mid+1] is not equal to k than we should return mid
elseif  k is greater than arr[mid] we should call the function recursively on the right half
else  k is smaller than arr[mid] we should call the function recursively on the left half
if element is not found return -1

 int first(int arr[], int low, int high, int k, int n) 
{ 
    if (high >= low) { 
        int mid = (low + high) / 2; 
        if ((mid == 0 || k > arr[mid - 1]) && arr[mid] == k) 
            return mid; 
        else if (k > arr[mid]) 
            return first(arr, (mid + 1), high, k, n); 
        else
            return first(arr, low, (mid - 1), k, n); 
    } 
    return -1; 
} 
  
 
int last(int arr[], int low, int high, int k, int n) 
{ 
    if (high >= low) { 
        int mid = (low + high) / 2; 
        if ((mid == n - 1 || k < arr[mid + 1]) && arr[mid] == k) 
            return mid; 
        else if (k < arr[mid]) 
            return last(arr, low, (mid - 1), k, n); 
        else
            return last(arr, (mid + 1), high, k, n); 
    } 
    return -1; 
} 

Time Complexity : O(log n)
Auxiliary Space : O(Log n)