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

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)