Find the First and Last Position of an Element in a Sorted Array

People who are involved in computer programming perform tabulation and allocation of massive amounts of data within seconds by the use of Arrays!

But, how is this possible?

Well, the basic purpose of designing an array is associated with identifying categories of similar data and sorting them in a specific order so that they are easier to locate. These data components are stored in the form of elements. 

Now, since these elements are stored in a linear structure, one cannot tell the beginning and end of the element by simply looking at the data structure.

This is essentially where the problem of finding the first and last position of an element in a sorted array arises. 

This problem can be effectively solved using different algorithms that we have discussed in the blog. 

So let's get started! 

What are Elements in an Array?

Arrays are one of the simplest forms of data structures that are used for storing and allocating of categories of data that have similar connotations.

That is why the contents of an array are often referred to as items or "elements". One of the main reasons for using the Array data structure is because it facilitates locating data in an efficient manner by the use of indexes.

Every element or cell contained in an Array has a pre-specified address that makes these elements easier to locate by simply using the Index Pointers.

Now, since this blog is all about finding the first and last position of elements in a sorted array, have a look at a brief discussion on sorted arrays and we shall move further to solving the problem statement.

What are Sorted Arrays?

Since arrays are data structures containing alphabetical, symbolic or numerical elements in general, the sorted arrays are used for arranging these elements in a specific order that either follows an ascending or descending path.

Also, the elements stored within a sorted array will be spaced equally in the computer's memory. 

In the context of computer programming, the sorted arrays assist in the implementation of the static lookup tables where multiple values of similar data types are stored effectively. 

Hence, the sorted arrays facilitate the organisation of data in an efficient manner. With the sorting of arrays, it becomes easier to locate, insert and iterate further on the data in future.

To demonstrate the “easier to locate” aspect of sorted arrays, we have discussed the problem statement of finding the first and last position of an element in a sorted array.

Here’s a list of some useful methods that can be implemented to locate the position of elements in a sorted array! 

How to find the First and Last position of an Element in a Sorted Array?

Have a look at the following problem statement related to finding and locating the first and last elements stored within a given sorted array.

Afterwards, we will have a look at the prospective methods and algorithms for solving this problem.

Problem Statement:

You have been given a sorted array i.e arr[]. This array possibly consists of duplicate elements. Your task is to figure out the position of the indexes of the first and last occurrences of a certain element "x" within the array.

This problem statement can be effectively solved using three different approaches. We have discussed the implementation and time complexities related to all the methods as follows.

Method 1: Implementing a Naive Approach

The initial idea of this approach is to integrate all the elements concerning the given array. 

We will have to keep track of all these elements in order to figure out the exact positions of the first and last occurrences of the concerned element or rather its index position.

Here's how the algorithm for this approach would work:

• You will have to start by running a loop through the entire course of the array from i = 0 and n -1
• First consider the = -1 occurrence and the last occurrence of = -1 
• When we first spot the given element "x" we will update its value to = i
• Similarly, the second spotting of the element will be stored as the last occurrence hence, updating last = i
• Finally, print the first and last occurrences and the program will be completed.

Time Complexity for this approach:

O(n)

Method 2: Making effective use of the Binary Search Approach

Did you know that the Binary Search Algorithm is also used in the context of other DSA problems such as merging two sorted arrays, finding zero-sum in a subarray, reversing a string and flattening a linked list?

The Binary Search approach is associated with evaluating the high, mid and low ranges of the characters of the given array.

For spotting the first occurrence of the required element, consider the following algorithm:

• If it is found to be (high>=low)
• Then you can calculate the value of mid as equal to low + (high-low)/2
• If the mid value is found to be equal to ==0 then you may proceed further and return mid;
• Else you may print -1;

Now for the second spotting of the element, the algorithm will work as follows:

• If it is found to be (high>=low)
• Then you can calculate the value of mid as equal to low + (high-low)/2
• If the mid value is found to be equal to == n - 1 then you may return mid;
• Otherwise, you can return -1 

Time Complexity for this approach:

O(log n)

Method 3: This is an iterative solution for the Binary Search Approach

Since we have already discussed the implementation of the algorithm for Binary Search above, let's overview the basis of the algorithm for this iterative approach:

• While spotting the first occurrence, we will have to figure out the location of the first index and further search the left subtree.
• For the second occurrence or rather the last occurrence, we will be iterating the right subtree as far as we are able to find the number.

Time Complexity for this approach:

This approach is slightly time efficient with O(log n) complexity.

Final Thoughts

If you are new to programming, reading this blog might have induced clarity on how the difficulty-level Data Structures and Algorithms are majorly overhyped.

Also, while we are on the subject of DSA, allow us to suggest looking up some other useful concepts such as finding zero sum subarray, searching a binary tree or flattening a linked list all mentioned in our other blogs!