Given a sorted array arr[] with possibly duplicate elements, write a program to find indexes of first and last occurrences of a target element in the given array.

Problem Note

  • The algorithm's runtime complexity must be in the order of O(log n).
  • If the target is not found in the array, return [-1, -1].

Example 1

Input: arr[] = [1, 3, 5, 5, 5, 5 ,28, 37, 42], target = 5
Output: [2, 5]
Explanation: First Occurrence = 2 and Last Occurrence = 5

Example 2

Input: arr[] = [1, 3, 5, 5, 5, 5 ,7, 28, 37], target = 7
Output: [6, 6]
Explanation: The first and the last index where 7 appears in arr[] is 6.

Example 3

Input: arr[] = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Explanation: The element 6 is not found in the given array. So, return [-1,-1].