Sri Mahalakshmi

Posted on Mar 22

Finding First and Last Occurrence of an Element Using Binary Search in Python

#python #beginners #programming

Problem Explanation

You are given a sorted array arr[] (may contain duplicates) and a number x.
Your task is to find the first and last occurrence of x.

If x is not found, return [-1, -1].

Example:

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

Method Used: Binary Search

Idea

Since the array is sorted:

Use binary search to find the first occurrence
Use binary search again to find the last occurrence

Why This Method?

Time complexity: O(log n)
Much faster than linear search (O(n))
Efficient for large arrays

Python Code with Explanation

class Solution:
    def find(self, arr, x):

Defines the function.

Finding First Occurrence

        left = 0
        right = len(arr) - 1
        first = -1

Initialize pointers and variable to store first occurrence.

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

Standard binary search setup.

            if arr[mid] == x:
                first = mid
                right = mid - 1

If found:

Store index
Move left to find earlier occurrence

            elif arr[mid] < x:
                left = mid + 1

Search in right half.

            else:
                right = mid - 1

Search in left half.

Finding Last Occurrence

        left = 0
        right = len(arr) - 1
        last = -1

Reset pointers and initialize last occurrence.

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

Binary search again.

            if arr[mid] == x:
                last = mid
                left = mid + 1

If found:

Store index
Move right to find later occurrence

            elif arr[mid] < x:
                left = mid + 1

Move right.

            else:
                right = mid - 1

Move left.

        return [first, last]

Return both indices.

Complete Code

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

        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == x:
                first = mid
                right = mid - 1
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1

        left = 0
        right = len(arr) - 1
        last = -1

        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == x:
                last = mid
                left = mid + 1
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1

        return [first, last]

Step-by-Step Example

Input:

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

Output:

[2, 5]

Key Takeaway

Using binary search twice helps efficiently find both first and last positions in a sorted array.

DEV Community