First & Last Occurences

Finding First and Last Occurrence in a Sorted Array

Problem

You’re given a sorted array (with possible duplicates) and a value x.
The task is to find the first and last occurrence of x.
If it doesn’t exist, return [-1, -1].

Strategy

A normal binary search can find x, but it doesn’t guarantee the first or last position.

So instead of stopping when I find the element, I keep going:

For the first occurrence, I continue searching on the left
For the last occurrence, I continue searching on the right

So the idea becomes:
run binary search twice, each time pushing toward a boundary.

Code

class Solution:
    def find(self, arr, x):
        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

        return [findFirst(arr, x), findLast(arr, x)]

Key Lines Explained

first = mid then right = mid - 1
Even after finding x, we move left to see if it appears earlier.
last = mid then left = mid + 1
Same idea, but moving right to find the last occurrence.
first = -1 / last = -1
These stay -1 if the element is never found.

Why This Works

Since the array is sorted, all occurrences of x are grouped together.

Binary search helps us reach that group quickly, and then we just push toward the edges of that group.

Complexity

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

Final Note

This problem is a small twist on binary search.

Instead of just finding an element, you’re finding its boundaries — and that small change makes a big difference in how you think about the search.

Forem