CA 19 - First & Last Occurences

Problem
First & Last Occurences
You are given a sorted array arr and a target value x.
Your task is to find the first and last occurrence of x.

If x is not present, return [-1, -1].

Input: [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5 → Output: [2, 5]
Input: [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7 → Output: [6, 6]
Input: [1, 2, 3], x = 4 → Output: [-1, -1]

Approach

Since the array is sorted, we can use Binary Search to efficiently find both positions.

Instead of stopping at the first match, we continue searching to find:

• The leftmost occurrence (first position)

• The rightmost occurrence (last position)
  Steps:

• Perform binary search to find the first occurrence:

• Move left when a match is found

• Perform binary search to find the last occurrence:

• Move right when a match is found

• If the element is not found, return [-1, -1]

This avoids scanning the entire array.

Complexity:
Time Complexity: O(log n)
Space Complexity: O(1)

def findFirst(arr, x):
    left, right = 0, len(arr) - 1
    first = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            first = mid
            right = mid - 1
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return first
def findLast(arr, x):
    left, right = 0, len(arr) - 1
    last = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            last = mid
            left = mid + 1
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return last
def firstAndLast(arr, x):
    return [findFirst(arr, x), findLast(arr, x)
arr = [1, 3, 5, 5, 5, 5, 67, 123, 125]
x = 5
print(firstAndLast(arr, x))