First & Last Occurences

lets first understand the question

We are given a sorted array which may contain duplicate elements
we are also given a number x, and we need to find:
the first occurrence of x
the last occurrence of x
we return the indices in the form:

[first_index, last_index]

if the element is not present, return
[-1, -1]

sample i/p and o/p

Input:
arr = [1, 3, 5, 5, 5, 5, 67, 123], x = 5

Output:
[2, 5]

how to approach the solution

I first thought →
"can I just loop through the array and find first and last?"
yes, but that will take O(n) time
since the array is already sorted, we can do better using binary search
instead of finding just one occurrence, we modify binary search to find the leftmost occurrence and rightmost occurrence it work by running a binary search twice

for first occurrence → move left when found
for last occurrence → move right when found

step by step
arr = [1, 3, 5, 5, 5, 5, 67]

find first:
mid = 5 → found → move left

continue until first position → index 2

find last:
mid = 5 → found → move right

continue until last position → index 5

approach
use binary search

when element is found:
update answer
continue searching in one direction

** Algorithm**

def searchRange(self, arr, x):

        def findFirst(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   # move left
                elif arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid - 1

            return ans

        def findLast(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   # move right
                elif arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid - 1

            return ans

        return [findFirst(arr, x), findLast(arr, x)]