CA 19 - First & Last Occurences

Problem

Given a sorted array arr[] with possible duplicates and an element x, the task is to find the first and last occurrences of x.

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

Output

Example 1
Output: [2, 5]
Example 2
Output: [6, 6]
Example 3
Output: [-1, -1]

My Approach

To solve this problem, I used Binary Search.

I perform binary search twice:

First to find the first occurrence of x
Second to find the last occurrence of x

For the first occurrence:

When I find x, I continue searching on the left side

For the last occurrence:

When I find x, I continue searching on the right side

This ensures that I get the exact boundaries of the element.

This approach is efficient because:

It reduces the search space logarithmically
It requires constant extra space
Code

def find_occurrences(arr, x):
    def first():
        left = 0
        right = len(arr) - 1
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == x:
                ans = mid
                right = mid - 1
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1
        return ans

    def last():
        left = 0
        right = len(arr) - 1
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == x:
                ans = mid
                left = mid + 1
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1
        return ans

    return [first(), last()]