First and Last Occurrence of an Element in a Sorted Array

Problem Statement:
Given a sorted array with duplicates, find the first and last occurrences of a given element. If the element is not present, return [-1, -1].

Example:
Input: [1, 3, 5, 5, 5, 5, 67], x = 5
Output: [2, 5]

Approach:
We use Binary Search twice:

First to find the first occurrence

Second to find the last occurrence

This ensures efficient searching in O(log n) time.

Code:

def firstOccurrence(arr, x):
low, high = 0, len(arr) - 1
result = -1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == x:
        result = mid
        high = mid - 1
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

return result

def lastOccurrence(arr, x):
low, high = 0, len(arr) - 1
result = -1

while low <= high:
    mid = (low + high) // 2
    if arr[mid] == x:
        result = mid
        low = mid + 1
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

return result

def findOccurrences(arr, x):
return [firstOccurrence(arr, x), lastOccurrence(arr, x)]
Explanation:
The first binary search finds the leftmost position, and the second finds the rightmost position of the element.

Time Complexity:
O(log n)

Space Complexity:
O(1)