CA 19 - First and Last Occurances

Problem Statement

Given a sorted array arr with possibly some duplicates, the task is to find the first and last occurrences of an element x in the given array.

Note: If the number x is not found in the array then return both the indices as -1.

Examples:

Input: arr[] = [1, 3, 5, 5, 5, 5, 67, 123, 125], x = 5
Output: [2, 5]
Explanation: First occurrence of 5 is at index 2 and last occurrence is at index 5.

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

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

My Goal

For this problem, my goal was to:

Efficiently find positions in a sorted array
Avoid linear search for better performance
Understand variations of binary search
Handle duplicate elements correctly

Solution

I used Binary Search twice:

To find the first occurrence
To find the last occurrence

Idea:

For first occurrence:

Move left even after finding the element
For last occurrence:
Move right even after finding the element

This ensures we capture the full range.

Solution Code (Python)

def find(a, x):
    n = len(a)

    # first occurrence
    l, h = 0, n - 1
    f = -1
    while l <= h:
        m = (l + h) // 2
        if a[m] == x:
            f = m
            h = m - 1
        elif a[m] < x:
            l = m + 1
        else:
            h = m - 1

    # last occurrence
    l, h = 0, n - 1
    s = -1
    while l <= h:
        m = (l + h) // 2
        if a[m] == x:
            s = m
            l = m + 1
        elif a[m] < x:
            l = m + 1
        else:
            h = m - 1

    return [f, s]


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

print(find(a, x))

Explanation

First binary search finds leftmost index
Second binary search finds rightmost index
If element not found → both remain -1