First & Last Occurences

Problem Statement

Given a sorted array arr and an integer x, find:

The first occurrence index of x
The last occurrence index of x

If x is not present, return:

[-1, -1]
Example 1

Input:

arr = [1, 3, 5, 5, 5, 5, 67, 123, 125]
x = 5

Output:

[2, 5]

Explanation:

First 5 appears at index 2
Last 5 appears at index 5
Example 2

Input:

arr = [1, 3, 5, 5, 5, 5, 7, 123, 125]
x = 7

Output:

[6, 6]
Example 3

Input:

arr = [1, 2, 3]
x = 4

Output:

[-1, -1]
Important Observation

The array is already sorted.

So instead of scanning the entire array (O(n)),
we can use Binary Search to achieve O(log n) time complexity.

Efficient Approach – Modified Binary Search (O(log n))

We perform two binary searches:

One to find the first occurrence
One to find the last occurrence
Why Two Binary Searches?

Normal binary search stops when it finds the element.

But we need:

The leftmost position
The rightmost position

So we modify the condition slightly.

Algorithm
To Find First Occurrence:
If arr[mid] == x
Store index
Move right = mid - 1 (search left side)
If arr[mid] < x
Move left = mid + 1
Else
Move right = mid - 1
To Find Last Occurrence:
If arr[mid] == x
Store index
Move left = mid + 1 (search right side)
If arr[mid] < x
Move left = mid + 1
Else
Move right = mid - 1
Python Implementation (Optimized – O(log n))
class Solution:

def firstOccurrence(self, arr, x):
    left = 0
    right = len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == x:
            result = mid
            right = mid - 1   # move left to find first occurrence
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

    return result


def lastOccurrence(self, arr, x):
    left = 0
    right = len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == x:
            result = mid
            left = mid + 1   # move right to find last occurrence
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

    return result


def find(self, arr, x):
    first = self.firstOccurrence(arr, x)
    last = self.lastOccurrence(arr, x)
    return [first, last]

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity: O(1)
Why This Is Efficient

Instead of checking every element:

Binary search cuts the search space in half each time.
Works perfectly because array is sorted.
Even if array size is 10⁶, solution runs efficiently.
Final Output Behavior
Case Output
Element present multiple times [first_index, last_index]
Element present once [index, index]
Element not present [-1, -1]