First And Last Occurence

In this task, I worked on finding the first and last positions of a given element in a sorted array.
Instead of scanning the entire array, I used a more efficient approach using Binary Search.

MY APPROACH
I created a function that takes:

• A sorted array
• A target element x

And returns:

• The first occurrence index
• The last occurrence index

EXAMPLE
Input : arr = [1, 2, 2, 2, 3, 4]
x = 2
output : [1,3]

HOW I SOLVED IT
To solve this effectively i used binary search twice,

1. To Find the first occurences, If element matches:
2. Store index
3. Move left to find earlier occurrence
4. To find the last occurences , If element matches:
5. Store index
6. Move left to find earlier occurrence

HOW IT WORKS
Binary search reduces the search space by half each time

• For first occurrence → we keep moving left
• For last occurrence → we keep moving right This ensures we find the exact boundaries

class Solution:
    def firstAndLast(self, arr, x):
        def findFirst(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
                elif arr[mid] < x:
                    low = mid + 1
                else:
                    high = mid - 1

            return first

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

            return last

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