First and Last Occurrences in a Sorted Array

First and Last Occurrences in a Sorted Array
Problem Statement

Given a sorted array that may contain duplicates, find the first occurrence and last occurrence of a given element x.

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

Examples
Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]

Input: arr = [1, 2, 3], x = 4
Output: [-1, -1]
Understanding the Problem

Since the array is sorted, we should not use linear search.
Instead, we use Binary Search to find:

First occurrence

Last occurrence

This reduces time complexity from O(n) → O(log n).

Approach 1: Linear Search (Simple but Slow)
Steps

Traverse array from beginning → first occurrence

Traverse from end → last occurrence

Return indices

Python Code
def first_last_linear(arr, x):
first = -1
last = -1

for i in range(len(arr)):
    if arr[i] == x:
        if first == -1:
            first = i
        last = i

return [first, last]

arr = [1,3,5,5,5,5,67,123,125]
print(first_last_linear(arr, 5))
Complexity
Time Space
O(n) O(1)
Approach 2: Binary Search (Optimal Method)

We perform binary search twice:

To find first occurrence

To find last occurrence

Binary Search for First Occurrence

If element found → move left to find earlier occurrence

Binary Search for Last Occurrence

If element found → move right to find later occurrence

Python Code (Optimal Solution)
def findFirst(arr, x):
low = 0
high = len(arr) - 1
first = -1

while low <= high:
    mid = (low + high) // 2

    if arr[mid] == x:
        first = mid
        high = mid - 1
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

return first

def findLast(arr, x):
low = 0
high = len(arr) - 1
last = -1

while low <= high:
    mid = (low + high) // 2

    if arr[mid] == x:
        last = mid
        low = mid + 1
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = 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]
print(firstAndLast(arr, 5))
Example Walkthrough
arr = [1, 3, 5, 5, 5, 5, 67]
x = 5

Binary search finds:

First occurrence → index 2

Last occurrence → index 5

Output:

[2, 5]
Complexity Analysis
Approach Time Space
Linear Search O(n) O(1)
Binary Search O(log n) O(1)

Best Approach → Binary Search

Key Concepts Learned

Binary Search

Searching in sorted array

First occurrence search

Last occurrence search

Time complexity optimization

Conclusion

To find first and last occurrences in a sorted array:

Use Binary Search

Run binary search twice

Time complexity becomes O(log n) which is very efficient

This is a very common interview and coding problem.