First and Last Occurences

Introduction

Finding the first and last occurrences of an element is a common problem in arrays. It is especially useful in searching and indexing tasks.

---

Problem Statement

Given a sorted array and a target value, find the first and last position of the target element.

If the element is not found, return [-1, -1].

---

Approach (Binary Search)

We use Binary Search twice:

1. First Binary Search → to find the first occurrence
2. Second Binary Search → to find the last occurrence

---

Python Code

python
def first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

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

        if arr[mid] == target:
            result = mid
            right = mid - 1   # search left side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


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

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

        if arr[mid] == target:
            result = mid
            left = mid + 1   # search right side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def search_range(arr, target):
    return [first_occurrence(arr, target),
            last_occurrence(arr, target)]

# Example
arr = [5, 7, 7, 8, 8, 10]
target = 8
print("Positions:", search_range(arr, target))


## Input
 arr = [5, 7, 7, 8, 8, 10]
target = 8

## output
[3,4]