CA 19 - First & Last Occurences

Problem Statement: here

Solution:

• First, we use a searching method that keeps dividing the array into halves because the array is already sorted.
• To find the first occurrence, whenever we see the number, we don’t stop. We remember its position and continue looking towards the left side to check if the same number appears earlier. We keep doing this until we can’t search anymore. This gives us the earliest position.
• Then, to find the last occurrence, we repeat the same process, but this time when we find the number, we remember it and continue searching towards the right side to see if it appears later. This gives us the final position.
• At the end, we return both positions. If the number was never found, both positions remain -1.

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   # go left
        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   # go right
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return ans
def find_positions(arr, x):
    first = first_occurrence(arr, x)
    last = last_occurrence(arr, x)
    return [first, last]