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 = 5 and last Arr = 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

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

``` 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)

darkmode