ASSIGNMENT 19

Find First and Last Occurrence in a Sorted Array (Binary Search)

Searching efficiently in a sorted array is a must-know skill.
Let’s solve a classic problem using Binary Search 👇

📌 Problem Statement

Given a sorted array arr, find the first and last occurrence of a given element x.

⚠️ Conditions:
If x is not found → return [-1, -1]
Must be efficient (better than linear search)
🧪 Examples
Example 1
Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]
Example 2
Input: arr = [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7
Output: [6, 6]
💡 Optimal Approach: Modified Binary Search

Instead of scanning the array, we use Binary Search twice:

Find first occurrence
Find last occurrence
🧠 Key Idea
For first occurrence:
Move left even after finding x
For last occurrence:
Move right even after finding x
🔄 Algorithm Steps
🔍 First Occurrence
If arr[mid] == x:
Store index
Move left (high = mid - 1)
🔍 Last Occurrence
If arr[mid] == x:
Store index
Move right (low = mid + 1)
💻 Python Implementation
def find_first(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 find_last(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

def find_occurrences(arr, x):
return [find_first(arr, x), find_last(arr, x)]

Example usage

arr = [1, 3, 5, 5, 5, 5, 67, 123, 125]
x = 5
print(find_occurrences(arr, x))
🧾 Output
[2, 5]
🔍 Dry Run (Quick Insight)

For:

[1, 3, 5, 5, 5, 5, 67]
First occurrence → keep moving left
Last occurrence → keep moving right
⚡ Complexity Analysis
Metric Value
Time Complexity O(log n)
Space Complexity O(1)

🏁 Conclusion

This problem shows how powerful Binary Search can be when slightly modified.