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)