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