First & Last Occurences

Introduction

Searching in a sorted array can be optimized using Binary Search.

This problem extends binary search to find not just one occurrence, but the first and last positions of a target element.

Problem Statement

Given a sorted array arr[] (may contain duplicates) and a value x,

Find:

• First occurrence of x
• Last occurrence of x

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

Examples

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, 5, 7, 123, 125], x = 7
Output: [6, 6]

Example 3:
Input: arr = [1, 2, 3], x = 4
Output: [-1, -1]

Intuition

Normal binary search finds any one occurrence

But we need:

• First occurrence → go left
• Last occurrence → go right

Approach

Algorithm Steps

Step 1: Find first occurrence

• If found, move left (high = mid - 1)

Step 2: Find last occurrence

• If found, move right (low = mid + 1)

Code (Python)

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

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

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

    return first


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

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

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

    return last


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

Step-by-Step Explanation

For x = 5:

• First occurrence → move left until smallest index
• Last occurrence → move right until largest index

Complexity Analysis

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

Conclusion

This problem is a great example of extending binary search for more advanced queries like range finding.