First and Last Position of an Element In Sorted Array

Easy

+9 more companies

Solve now

Problem statement

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.

Now, your task is to find the first and last occurrence of ‘k’ in 'arr'.

Note :

1. If ‘k’ is not present in the array, then the first and the last occurrence will be -1. 
2. 'arr' may contain duplicate elements.

Example:

Input: 'arr' = [0,1,1,5] , 'k' = 1

Output: 1 2

Explanation:
If 'arr' = [0, 1, 1, 5] and 'k' = 1, then the first and last occurrence of 1 will be 1(0 - indexed) and 2.

Input Format

The first line of each test case contains two single-space separated integers ‘n’ and ‘k’, respectively.

The second line of each test case contains ‘n’ single space-separated integers denoting the elements of the array/list 'arr'.

Output Format :

Return two single-space separated integers denoting the first and the last occurrence of ‘k’ in 'arr', respectively.

Note:

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

Solve now

Approaches

01 Approach

Naively traverse the array and find the first and last occurrence of ‘K’ in ARR.

Solve now

02 Approach

The main intuition behind this approach is that ‘ARR’ is already sorted. So, we will modify the binary search algorithm and find the first occurrence and last occurrence of ‘K’ in ‘ARR’.

Here is the algorithm:

We initialise two integer variables ‘first’ and ‘last’ to -1. They store the first and last occurrence of ‘K’, respectively.

We initialise two integer variables ‘si’ and ‘ei’ denoting the start index and the end index to 0 and N -1, respectively.

The modified binary search to find the first occurrence of ‘K’ :

We find the index of the middle element of ARR as mid = si + (ei - si) /2 .
If (ARR[mid] == K)
1. first = mid
2. We update the end index, ei = mid - 1.
Else If (ARR[mid] < K)
1. We update the start index, si = mid + 1.
Else
1. We update the end index, ei = mid - 1.

The modified binary search to find the last occurrence of ‘K’ :

We find the index of the middle element of ARR as mid = si + (ei - si) / 2
If (ARR[mid] == K)
1. last = mid
2. We update the start index, si = mid + 1.
Else If (ARR[mid] < K)
1. We update the start index, si = mid + 1.
Else If (ARR[mid] > K)
1. We update the end index, ei = mid - 1.