First & Last Occurences

In this task, I worked on finding the first and last positions of a given number in a sorted array.

Instead of scanning the entire array, I used binary search to do it efficiently.

What I Did

I created three functions:

• first_occurrence() → finds the first position of the element
• last_occurrence() → finds the last position of the element
• find_positions() → combines both results

How I Solved It

I used binary search twice, with a small twist:

1. Finding First Occurrence

• If I find the target, I store the index
• Then I continue searching on the left side (because there might be an earlier occurrence)

2. Finding Last Occurrence

• If I find the target, I store the index
• Then I continue searching on the right side (because there might be a later occurrence)

Key Idea

• Move left (high = mid - 1) → to find first occurrence
• Move right (low = mid + 1) → to find last occurrence

Code

def first_occurrence(arr, x):
    low, high = 0, len(arr) - 1
    ans = -1

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

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

    return ans


def last_occurrence(arr, x):
    low, high = 0, len(arr) - 1
    ans = -1

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

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

    return ans


def find_positions(arr, x):
    return [first_occurrence(arr, x), last_occurrence(arr, x)]

How It Works

The algorithm keeps reducing the search space by half each time.

• First function pushes toward the left boundary
• Second function pushes toward the right boundary

So instead of checking every element, it quickly locks onto both ends of the target range.

Time Complexity

• Each binary search → O(log n)
• Total → O(log n)

Example Output

[2, 5]
[6, 6]
[-1, -1]