First and Last Occurrence in a Sorted Array (Binary Search Explained)

Introduction

Searching problems become more interesting when duplicates are involved. Instead of just finding an element, we sometimes need to find its first and last occurrence.

This problem is a great application of Binary Search with a twist.

Problem Statement

Given a sorted array arr with possible duplicates and a target x, find:

• The first occurrence of x
• The last occurrence 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]

---

Example 2

Input:

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

Output:

[6, 6]

Example 3

Input:

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

Output:

[-1, -1]

Key Idea

Since the array is sorted, we can use Binary Search.

But instead of stopping when we find the element:

• For first occurrence keep searching left
• For last occurrence larger so keep searching right

Approach

We perform Binary Search twice:

1. Find First Occurrence

• If arr[mid] == x, store index and move left
• Else adjust search space normally

2. Find Last Occurrence

• If arr[mid] == x, store index and move right

Python Implementation

def find_first(arr, x):
    low, high = 0, len(arr) - 1
    result = -1

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

        if arr[mid] == x:
            result = mid
            high = mid - 1  # move left
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return result


def find_last(arr, x):
    low, high = 0, len(arr) - 1
    result = -1

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

        if arr[mid] == x:
            result = mid
            low = mid + 1  # move right
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return result


def first_last_occurrence(arr, x):
    return [find_first(arr, x), find_last(arr, x)]


# Example usage
arr = [1, 3, 5, 5, 5, 5, 67, 123, 125]
print(first_last_occurrence(arr, 5))

Step-by-Step Insight

For x = 5:

• First occurrence search left until smallest index
• Last occurrence search right until largest index

Why This Works

• Sorted array allows binary search
• Modified conditions help track boundaries
• Efficient even for large datasets

Key Points

• Binary Search can be modified for boundary problems
• Always continue searching after finding the element

• Useful in many problems like:

  • Count occurrences
  • Range queries

Conclusion

This problem extends the idea of Binary Search by finding boundaries instead of just existence. Mastering this variation is important for solving many advanced search-related problems efficiently.