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
Top comments (0)