Finding First and Last Occurrence of an Element Using Binary Search in Python

Problem Explanation You are given a sorted array arr[] (may contain duplicates) and a number x. Your task is to find the first and last occurrence of x. If x is not found, return [-1, -1]. Example: Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5 Output: [2, 5] Input: arr = [1, 3, 5, 5, 5, 7, 123, 125], x = 7 Output: [6, 6] Method Used: Binary Search Idea Since the array is sorted: Use binary search to find the first occurrence Use binary search again to find the last occurrence Why This Method? Time complexity: O(log n) Much faster than linear search (O(n)) Efficient for large arrays Python Code with Explanation class Solution: def find(self, arr, x): Defines the function. Finding First Occurrence left = 0 right = len(arr) - 1 first = -1 Initialize pointers and variable to store first occurrence. while left <= right: mid = (left + right) // 2 Standard binary search setup. if arr[mid] == x: first = mid right = mid - 1 If found: Store index Move left to find earlier occurrence el