CA 19 - First & Last Occurences

1.Problem Understanding

Given sorted array we need to find the first occurance and last occurance of the duplicates

if not found → return [-1, -1]

Example

arr = [1, 3, 5, 5, 5, 67, 123]

x = 5

Output:

[2, 4]

2.Idea

One for first occurrence

One for last occurrence

First Occurrence:

When you find x

don’t stop

move LEFT to find earlier occurrence

Last Occurrence:

When you find x

don’t stop

move RIGHT to find later occurrence

3.Example

Array:

[1, 3, 5, 5, 5, 67]

Searching for 5

First occurrence:

Keep going LEFT

Last occurrence:

Keep going RIGHT

4.Algorithm

First Occurrence:

If arr[mid] == x

→ store index

→ move right = mid - 1

Last Occurrence:

If arr[mid] == x

→ store index

→ move left = mid + 1