Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 9 Jan, 2021

Easy

```
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.
```

```
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.
```

```
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'.
```

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

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

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

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*)*first = mid*- We update the end index
*, ei = mid - 1.*

- Else If (
*ARR[mid]*<*K*)- We update the start index
*, si = mid + 1.*

- We update the start index
- Else
- We update the end index,
*ei = mid - 1.*

- We update the end index,

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*)*last = mid*- We update the start index
*, si = mid + 1.*

- Else If (ARR[mid] < K)
- We update the start index,
*si = mid + 1.*

- We update the start index,
- Else If (ARR[mid] > K)
- We update the end index,
*ei = mid - 1.*

- We update the end index,

Similar problems

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023