First and Last Occurrence in Sorted Array – Python

🔍 First and Last Occurrence in Sorted Array – Python (Binary Search)

Hi All,

Today I solved an important problem: Find the first and last occurrence of an element in a sorted array.

---

📌 Problem Statement

Given a sorted array arr[] and a number x, find:

• First occurrence index of x
• Last occurrence index of x

👉 If x is not found → return [-1, -1]

---

🔍 Examples

Example 1:

arr = [1, 3, 5, 5, 5, 5, 67, 123, 125]
x = 5

Output:

[2, 5]

---

Example 2:

arr = [1, 3, 5, 5, 5, 5, 7, 123, 125]
x = 7

Output:

[6, 6]

---

Example 3:

arr = [1, 2, 3]
x = 4

Output:

[-1, -1]

---

💡 Approach

🔹 Binary Search (Optimal)

👉 Instead of linear search (O(n)), we use:

• Binary search to find first occurrence
• Binary search to find last occurrence

---

🧠 Step-by-Step Logic

🔸 First Occurrence:

• Move left when element is found

🔸 Last Occurrence:

• Move right when element is found

---

💻 Python Code

def find_first(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 find_last(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_occurrences(arr, x):
    return [find_first(arr, x), find_last(arr, x)]

---

🔍 Dry Run

For:

arr = [1, 3, 5, 5, 5, 5, 7]
x = 5

Steps:

• First occurrence → index 2
• Last occurrence → index 5

---

🖥️ Sample Output

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

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

---

⚡ Complexity Analysis

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

---

🧠 Why this is important?

• Uses binary search variation
• Common interview question
• Helps in range queries

---

✅ Conclusion

This problem helped me understand:

• Modified binary search
• Handling duplicates in arrays
• Efficient searching

🚀 Must-know problem for coding interviews!

---