First and Last Occurrence in Sorted Array

Hi everyone!
Today I worked on a problem where we need to find the first and last position of an element in a sorted array. It’s a great example of modifying binary search.

Problem
Given a sorted array, find the first and last occurrence of a given element x.

If not found, return [-1, -1].

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

Output: [2, 5]

My Approach

At first, I thought of scanning the array, but that would take O(n) time.

Since the array is sorted, I used:

Binary Search (twice)

Logic
*Use binary search to find:

1. First occurrence *Move left even after finding element
2. Last occurrence *Move right even after finding element

Code (Python)
class Solution:
def find(self, arr, x):

    def first_occurrence():
        l, r = 0, len(arr) - 1
        ans = -1

        while l <= r:
            mid = (l + r) // 2

            if arr[mid] == x:
                ans = mid
                r = mid - 1
            elif arr[mid] < x:
                l = mid + 1
            else:
                r = mid - 1

        return ans

    def last_occurrence():
        l, r = 0, len(arr) - 1
        ans = -1

        while l <= r:
            mid = (l + r) // 2

            if arr[mid] == x:
                ans = mid
                l = mid + 1
            elif arr[mid] < x:
                l = mid + 1
            else:
                r = mid - 1

        return ans

    return [first_occurrence(), last_occurrence()]

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

Key Insight
Normal binary search stops at first match,
but here we continue searching to find boundaries.

What I Learned
Binary search can be modified for different needs
Sorted arrays give huge optimization advantage
Boundary problems are very common in interviews

Thanks for reading!
Feel free to share any other optimized approaches.