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

This problem is a classic application of Binary Search, where instead of finding just one occurrence, we find the first and last positions of an element.

---

📌 Problem Statement

Given a sorted array arr[] (with possible duplicates) and a target x, find:

• The first occurrence index
• The last occurrence index

If x is not present, return [-1, -1].

---

🔍 Examples

Example 1:
Input: [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]

Example 2:
Input: [1, 3, 5, 5, 5, 5, 7, 123, 125], x = 7
Output: [6, 6]

Example 3:
Input: [1, 2, 3], x = 4
Output: [-1, -1]

---

🧠 Intuition

A normal binary search finds any one occurrence.
But here we need:

• The leftmost (first) occurrence
• The rightmost (last) occurrence

👉 So we modify binary search slightly.

---

🔄 Approach (Modified Binary Search)

We perform two binary searches:

1. First occurrence:

• Move left even after finding the element

1. Last occurrence:

• Move right even after finding the element

---

💻 Python Code

```python id="fl1"
def first_occurrence(arr, x):
low, high = 0, len(arr) - 1
result = -1

while low <= high:
    mid = (low + high) // 2

    if arr[mid] == x:
        result = mid
        high = mid - 1  # move left
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

return result

def last_occurrence(arr, x):
low, high = 0, len(arr) - 1
result = -1

while low <= high:
    mid = (low + high) // 2

    if arr[mid] == x:
        result = mid
        low = mid + 1  # move right
    elif arr[mid] < x:
        low = mid + 1
    else:
        high = mid - 1

return result

def find_positions(arr, x):
return [first_occurrence(arr, x), last_occurrence(arr, x)]

print(find_positions([1, 3, 5, 5, 5, 5, 67, 123, 125], 5))

---

🧾 Dry Run

For: arr = [1, 3, 5, 5, 5, 5, 67], x = 5

First Occurrence:

* mid hits 5 → keep searching left → index = 2

Last Occurrence:

* mid hits 5 → keep searching right → index = 5

👉 Final Output: [2, 5]

---

⚡ Complexity

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

---

🔥 Why This Works

* Uses binary search efficiently
* Avoids full traversal (O(n))
* Works well with duplicates

---

⚠️ Edge Cases

* Element not present → [-1, -1]
* Only one occurrence → same index
* All elements same

---

🏁 Conclusion

This problem strengthens your understanding of:

* Binary search variations
* Handling duplicates
* Efficient searching