Find first and last position of element in sorted array.
Given a sorted array which contains duplicate elements. Write a code to find first and last position of a number in a sorted array.
OR
Find first and last occurrences of x in sorted array where x is a target value.
If a number is not found return -1.
For example –
Example 1 –
Input : {1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13, 13} , target = 11
Output: {5, 8}
The first index of 11 is 5 and last index is 8.
Example 2 –
Input: {1, 6, 7, 7, 8, 8, 9, 9}, target = 5
Output: {-1, -1}
The target value is not found.
NOTE – We have to solve this problem in O(logn) time complexity.