ASSIGNMENT 19

1. First and Last occureneces

Problem

Given a sorted array with possible duplicate elements, find the first and last occurrence of a given element x.

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

Example

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

Output:
[2, 5]

First occurrence at index 2 and last at index 5 

Approach Used
Modified Binary Search (Optimal Approach)

Since the array is sorted, we can use binary search instead of linear traversal.

Key Idea:
• Use binary search twice
• Once to find first occurrence
• Once to find last occurrence

This ensures efficient searching in O(log n) time 

Step-by-Step Explanation

Step 1: Understand the Goal

We are not just finding the element —
we need:
• Leftmost index (first occurrence)
• Rightmost index (last occurrence)

Step 2: Apply Binary Search for First Occurrence
• Start with full array
• When you find the element:
• Don’t stop immediately
• Move towards the left side to check if it appears earlier

Continue until you get the leftmost position

Step 3: Apply Binary Search for Last Occurrence
• Again start binary search
• When element is found:
• Move towards the right side

Continue until you get the rightmost position

Step 4: Combine Results
• Store both indices
• If element is not found → return [-1, -1]

CODE:

`class Solution:
def find(self, arr, x):
def first_occurrence():
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 last_occurrence():
        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 [first_occurrence(), last_occurrence()]`

Complexity Analysis

Type Complexity
Time O(log n)
Space O(1)

Conclusion

This problem is a classic example of how binary search can be extended beyond simple searching. Instead of stopping at the first match, we continue searching in a specific direction to find the boundaries of the element.