Find First and Last Occurrences in a Sorted Array

Problem Given a sorted array arr that may contain duplicates, find the first and last occurrence of a target element x. If x is not present, return [-1, -1]. Examples Input arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5 Output [2, 5] Explanation: First occurrence of 5 is at index 2, last at index 5. Input arr = [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7 Output [6, 6] Explanation: First and last occurrence of 7 is at index 6. Input arr = [1, 2, 3], x = 4 Output [-1, -1] Explanation: 4 is not present. Approach Use binary search to find the first occurrence of x. Use binary search again to find the last occurrence. If x is not found in either step, return [-1, -1]. This is efficient because the array is sorted, giving O(log n) time complexity. Python Code class Solution: def find(self, arr, x): n = len(arr) first = -1 last = -1 # Find first occurrence low = 0 high = n - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == x: first = mid high = mid - 1 elif arr[mid] < x: low = mid