# First and last occurrence of an element

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.

**Problem description:**

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.

**Input:**

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.

**Output:**

Print index of the first and last occurrences of the number *x* with a space in between.

**Constraints:**

1<=T<=1000
1<=n,a[i]<=100005

**Examples:**

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 elementx.b) Binary Search Approach:In this approach we will use the concept of binary search, for finding the first occurrence of the element

we follow:x, then we will store it in some variable first, and then we will do our further search operation on the left side of the mid-point.mid=(l+r)/2i.e.

.r=mid-1For finding the last occurrence of the element x we will perform:

, then we will store it in some variable second, and then we will do our further search operation on the right side of the mid-point.mid=(l+r)/2i.e.

.l=mid+1Time Complexityfor the above approach in the worst case is:O(logn)Space Complexityfor the above approach in the worst case is:O(1)C++ Implementation (Brute Force Approach):Output:C++ Implementation (Binary Search Approach):

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: