First and Last Occurrences - CA19

First and Last Occurrences – CA23

My Thinking and Approach

---

Introduction

In this problem, I was given a sorted array with possible duplicates and asked to find the first and last occurrences of a given element.

---

Problem Statement

• Given a sorted array arr

• Given an element x

• Find:

  • First occurrence of x
  • Last occurrence of x

• If element is not found:

  • Return [-1, -1]

---

My Initial Thought

At first, I considered:

• Traversing the array
• Recording first and last positions

But this approach takes more time.

---

Key Observation

Since the array is sorted:

• I can use binary search
• Modify it to find first and last positions

---

Optimized Approach

I decided to use binary search twice.

Logic:

• First binary search → find first occurrence
• Second binary search → find last occurrence

---

My Approach (Step-by-Step)

1. Use binary search to find first occurrence:

• If element found → move left to check earlier index

1. Use binary search to find last occurrence:

• If element found → move right to check later index

1. Return both indices

---

Code (Python)

Below is the implementation clearly separated inside a code block:

class Solution:
    def find(self, arr, x):
        def firstOccurrence():
            left, right = 0, len(arr) - 1
            result = -1

            while left <= right:
                mid = (left + right) // 2

                if arr[mid] == x:
                    result = mid
                    right = mid - 1
                elif arr[mid] < x:
                    left = mid + 1
                else:
                    right = mid - 1

            return result

        def lastOccurrence():
            left, right = 0, len(arr) - 1
            result = -1

            while left <= right:
                mid = (left + right) // 2

                if arr[mid] == x:
                    result = mid
                    left = mid + 1
                elif arr[mid] < x:
                    left = mid + 1
                else:
                    right = mid - 1

            return result

        return [firstOccurrence(), lastOccurrence()]

---

Example Walkthrough

Input:

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

Steps:

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

Output:

[2, 5]

---

Complexity Analysis

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

---

Key Takeaways

• Binary search can be modified for range queries
• Sorted arrays help reduce complexity
• Avoid linear search for better performance

---

Conclusion

This problem helped me understand how to use binary search effectively to find boundaries of an element in a sorted array.

---