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