First and last occurrences

Finding First and Last Occurrence Using Binary Search

When working with sorted arrays, a common problem is to find the first and last position of a given element x.

A straightforward approach is to scan the entire array, but that takes linear time. A more efficient solution uses binary search, which significantly reduces the time complexity.

Why This Approach?

1. The brute-force method checks every element in the array, resulting in a time complexity of O(n). This becomes inefficient as the size of the array grows.
2. Binary search works on sorted arrays and reduces the search space by half in every step. This brings the time complexity down to O(log n), making it much faster and scalable.

Key Idea

Instead of searching for just one occurrence of x, we perform two separate binary searches:

One to find the first (leftmost) occurrence
One to find the last (rightmost) occurrence
Code Overview

class Solution:
    def find(self,arr,x):
        def first(arr, x):
            low, high, res = 0, len(arr)-1, -1
            while low <= high:
                mid = (low+high)//2
                if arr[mid] == x:
                    res = mid
                    high = mid-1
                elif arr[mid] < x:
                    low = mid+1
                else:
                    high = mid-1
            return res

        def last(arr, x):
            low, high, res = 0, len(arr)-1, -1
            while low <= high:
                mid = (low+high)//2
                if arr[mid] == x:
                    res = mid
                    low = mid+1
                elif arr[mid] < x:
                    low = mid+1
                else:
                    high = mid-1
            return res
        return [first(arr, x), last(arr, x)]

Step-by-Step Explanation

1. Initialization

In both helper functions:
low, high, res = 0, len(arr)-1, -1
low and high define the search boundaries.
res stores the result index. It starts as -1 to indicate "not found".

1. Binary Search Loop while low <= high: mid = (low+high)//2 The loop continues until the search space is exhausted. mid is the middle index of the current range. Finding First Occurrence

When the element is found:

if arr[mid] == x:
res = mid
high = mid-1

Even after finding x, the search continues on the left side. This ensures that we locate the earliest position where x appears.

Other cases:

If arr[mid] < x, move right (low = mid + 1)
If arr[mid] > x, move left (high = mid - 1)
Finding Last Occurrence

The logic is almost identical, except for one change:

if arr[mid] == x:
res = mid
low = mid+1

After finding x, the search continues on the right side to find the last occurrence.

Other conditions remain the same.

Example

Input:

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

Output:

[1, 3]
First occurrence is at index 1
Last occurrence is at index 3

Why This Works Well

1. Binary search reduces the number of comparisons drastically by eliminating half of the search space in every iteration.
2. By slightly modifying the conditions, we can adapt it to find boundaries (first and last positions) instead of just checking for existence.