1. Education

Finding first and last position of element in sorted array

Disclaimer: This is a user generated content submitted by a member of the WriteUpCafe Community. The views and writings here reflect that of the author and not of WriteUpCafe. If you have any complaints regarding this post kindly report it to us.

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

  1. Run a for loop and for i = 0 to n-1
  2. Take first = -1 and last = -1 
  3. When we find element first time then we update first = i 
  4. We always update last=i whenever we find the element.
  5. 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.

Output:

Time Complexity : O(log n) 

Auxiliary Space : O(Log n) 

 

Conclusion

In this article, we have discussed a problem to find first and last position of element in sorted array using Naive’s as well as binary search approach.

Happy Learning!

Login

Welcome to WriteUpCafe Community

Join our community to engage with fellow bloggers and increase the visibility of your blog.
Join WriteUpCafe