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].