Given a sorted array A[] with possibly duplicate elements, write a program to find indexes of first and last occurrences of an element k 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: A[] = [1, 3, 5, 5, 5, 5 ,28, 37, 42], k = 5
Output: [2, 5]
Explanation: First Occurrence = 2 and Last Occurrence = 5

Example 2

Input: A[] = [1, 3, 5, 5, 5, 5 ,7, 28, 37], k = 7
Output: [6, 6]

Example 3

Input: A[] = [5,7,7,8,8,10], k = 6
Output: [-1,-1]