We have a sorted array with duplicate elements, the task is to find indexes of first and last occurrences of an element item in the given array.

Examples:

Input : arr[] = {1, 1, 2, 2, 2, 3, 4, 7, 8, 8}    
        item = 5
Output : First Occurrence = 2
         Last Occurrence = 4

Input : arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }    
        item = 7
Output : First Occurrence = 6
         Last Occurrence = 6

The Naive Approach is to run a for loop and check given elements in array.

1. Run a for loop and for i = 0 to n-1
2. Take start = -1 and end = -1 
3. When we find element first time then we update start = i 
4. We always update end = i whenever we find the element.
5. We return a array two value of occurances.

int* Bns_Occurances(int arr[], int n, int x) {
  int start = -1, end = -1, i = -1;
  while(++i < n) {
    if (x != arr[i])
        continue;
    if (start == -1)
        start = i;
    end = i;
  }
  int* occurances = (int *)malloc(2*sizeof(int));
  occurances[0] = start, occurances[1] = end;
  return occurances;
}

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

We can leverage binary search here to solve this problem.

If we found item we looking for in the array then we have stored the index in the variable result at which we found item. Then we do not stop our search.

If we need first occurrence then keep on searching before mid element. so end = mid - 1;

And start = mid + 1 when we are looking for last occurrence of number;

  
  a) while (start <= end)
  b) Calculate  mid = start + (end - start)/2;
  c) If (arr[mid] == item)
         result = mid;
         end = mid - 1;   // for first occurance
         start = mid + 1; // for last occurance
  d) Else if (item < arr[mid])
          end = mid - 1;
  e) Else
          start = mid + 1;
  f) finally return result; 

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