Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.
The problem wants you to find the position (index) first occurrence and last occurrence of the element x given in the problem. The main catch here is to use the fact that array is already sorted.
The first line consists of an integer T i.e. number of test cases. The first line of each test case contains two integers n and x. The second line contains n spaced integers.
Print index of the first and last occurrences of the number x with a space in between.
Input: T=1 N=9,x=3 [1,2,3,3,3,3,3,3,33] Output: 2 7, since 3 occurs at index 2 and 7. Input: T=1 N=8,x=5 [1,2,3,5,5,5,7,8] Output: 3 5, since 5 occurs at index 3 and 5.
(a) Brute Force Approach:
The problem can be solved using the naive algorithm, we will travel from first to the last element of the array, which will take O(n) time for traversal and store the first and last occurrence of the element x.
b) Binary Search Approach:
In this approach we will use the concept of binary search, for finding the first occurrence of the element x we follow:
For finding the last occurrence of the element x we will perform:
Time Complexity for the above approach in the worst case is: O(logn)
Space Complexity for the above approach in the worst case is: O(1)
C++ Implementation (Brute Force Approach):
C++ Implementation (Binary Search Approach):