Find First and Last Positions of an Element in a Sorted Array

Given a sorted array ARR consisting of N integers and an integer X, find the first and last positions of occurrence of X in the array.

Note:

1. The array follows 0-based indexing, so return 0-based indices.
2. If X is not present in the array, return “-1 -1”.
3. If X is only present once in the array, the first and last position of its occurrence will be the same.

Follow Up:

Try to solve the problem in O(log(N)) time complexity.

Input Format:

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains the integer N, the size of the sorted array.
The second line contains N space-separated integers denoting the array elements.
The third and last line contains the value X, whose first and last position of occurrence you need to find.

Output Format:

The only line of output of each test case should contain two space-separated integers: the first and the last position of occurrence of X in the array.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10⁴
• -10⁹ <= ARR[i] <= 10⁹
• -10⁹ <= X <= 10⁹

Time Limit: 1 sec

Note:

Just implement the given function. You do not need to print anything, it has already been taken care of.