Finding first and last position of element in sorted array

Problem Statement

Given an array of integers nums sorted in non-decreasing order, write a code to find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.

Example:

Input :

A[] = [21,32,46,75,98]

Target = 75

Output :

First Occurrence : 3

Last Occurrence : 3

Input :

A[] = {1, 2, 4, 4, 4, 4, 6, 56, 97}

target = 4

Output :

First Occurrence = 2

Last Occurrence = 5

Discussed Solution Approaches

We have a sorted array with possibly duplicate elements where we have to find indexes of first and last occurrences of an element x in the given array.We will discuss two approaches to solve this problem.

Naive Solution Approach
Binary Search Solution

Naive solution

A very basic approach to solve this problem is to run a for loop and check given elements in an array. Give below are the steps for the solution using naive approach

Run a for loop and for i = 0 to n-1
Take first = -1 and last = -1
When we find element first time then we update first = i
We always update last=i whenever we find the element.
We print first and last occurrence of the target.

Output

Time complexity: O(n)

Auxiliary Space: O(1)

Binary Search solution

A simple solution would be to run a linear search on the array and return the given element’s first or last occurrence. The problem with this approach is that its worst-case time complexity is O(n), where n is the size of the input. This solution also does not take advantage of the fact that the input is sorted. We can easily solve this problem in O(log(n)) time by modifying the binary search algorithm.