How to Find First & Last Position of Element in Sorted Array?

 

Binary Search is one of the most important topics asked in interviews. It helps you to find the targeted value in O(log(n)) time complexity. The only condition is that the array should be sorted. In this article, we will learn how to find the First and Last Positions of Elements in a Sorted Array with implementation in C++, Java, and Python.

First and Last Position Of Elements in Sorted Array

In this problem, we are given a sorted array and a target element. We have to find its first and the last position in the array. It might be possible that the element is not contained in the array. In that case, you will return [-1, -1].

Let’s understand this with an example.

Input: array = [2, 3, 4, 4, 4, 5, 6, 6], tar = 4

Output: [2, 4]

Explanation: We found the first 4 at index 2 and the last at index 4.

Input: array = [2, 3, 4, 4] tar = 3

Output: [1, 1]

Explanation: Only one 3 is present in the whole array so the first and the last position of 3 is 1.

The naive approach is to iterate the whole array and find the first and last position of the element. In this approach, you have to check every element present in the array which is laid to O(n) time complexity. Here’s how we will do it:

1. First, create two variables first and last. Initialize both with -1.
2. Now iterate over the array and check if the current value is the same as the target. 
3. Update the last element with the current index.
4. If it is check if the value of the first variable is -1 or not. If it is updated -1 with the current index otherwise continue.
5. Return the first and last variable as the answer.

The time complexity will be O(n) where n is the size of the array. We are iterating over the array which took O(n) time complexity. The space complexity is O(1) as we are not using any extra space.

Optimized Binary Search Approach

In the above approach, we are using O(n) time complexity. But as we know the array is sorted so we can apply binary search on this. This will reduce our time complexity to O(log(n)).

We will first find the first position using binary search and then find the last position using the same approach. Here are the steps:

1. First, create a function that will take an array, target, and flag. If the flag value is 0 means we are finding the first position of the target element otherwise we are finding the last position.
2. Now call the function for finding the first position.
3. Create two variables start = 0 and end = array. size()-1. Now keep on iterating till the start <=end. 
4. Now find the mid element by mid = (start + end)/2. Check if the element present at the middle index is less than the target element or not.
5. If it is less than the target element then our target element will be present on the right side or not present at all. So we will update start = mid+1.
6. If it is greater than the target element then our target will be present on the left side or not present at all. So we will update end = mid-1.
7. If it is equal to the target then check whether we are finding the first or last position. If we are finding the first position update the end = mid-1. Otherwise update start = mid+1.

Let’s examine the code for the above process.

C++ Code

Here is the C++ solution:

#include<bits/stdc++.h>

using namespace std;

int binary_search(vector<int>& v,int target, int p){

    int r=v.size();

    int start=0,end=r-1,ans=-1;

    while(start<=end){

        int mid=start+((end-start)/2);

            if(target > v[mid]){

            start=mid+1;

        }

        else if(target < v[mid]){

            end=mid-1;

        }

        else {

            ans=mid;

            if(p)start=mid+1;

            else end=mid-1;

        }

    }

    return ans; 

}

int main(){

    vector<int>arr = {2, 3, 4, 4, 4, 5, 5, 6};

    int target = 4;

    int first = binary_search(arr, target, 0);

    int last = binary_search(arr, target, 1);

    cout<<"First position of "<<target<<" is: "<<first<<endl;

    cout<<"Last position of "<<target<<" is: "<<last<<endl;

    return 0;

}

Java Code

Below is the Java program to find first and last position of elements in sorted array:

import java.util.*;

public class Main {

    public static int binarySearch(ArrayList<Integer> v, int target, int p) {

        int r = v.size();

        int start = 0, end = r - 1, ans = -1;

        while (start <= end) {

            int mid = start + (end - start) / 2;

            if (target > v.get(mid)) {

                start = mid + 1;

            } else if (target < v.get(mid)) {

                end = mid - 1;

            } else {

                ans = mid;

                if (p == 1) start = mid + 1;

                else end = mid - 1;

            }

        }

        return ans;

    }

    public static void main(String[] args) {

        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2, 3, 4, 4, 4, 5, 5, 6));

        int target = 4;

        int first = binarySearch(arr, target, 0);

        int last = binarySearch(arr, target, 1);

        System.out.println("First position of " + target + " is: " + first);

        System.out.println("Last position of " + target + " is: " + last);

    }

}

Python Code

Here is the Python program as well:

def binary_search(v, target, p):

    r = len(v)

    start, end, ans = 0, r - 1, -1

    while start <= end:

        mid = start + (end - start) // 2

        if target > v[mid]:

            start = mid + 1

        elif target < v[mid]:

            end = mid - 1

        else:

            ans = mid

            if p == 1:

                start = mid + 1

            else:

                end = mid - 1

    return ans

if __name__ == "__main__":

    arr = [2, 3, 4, 4, 4, 5, 5, 6]

    target = 4

    first = binary_search(arr, target, 0)

    last = binary_search(arr, target, 1)

    print("First position of", target, "is:", first)

    print("Last position of", target, "is:", last)

Output: 

First position of 4 is: 2
Last position of 4 is: 4

The time complexity for the above code is O(log(n)). We are dividing the array into half at every step and comparing the middle value of that divided array. The space complexity is O(1) as we are not using any extra space.

Here is a comparison to show how the binary search approach to find in a sorted array is better:

Conclusion

In this article, we have seen various approaches for finding the first and the last positions of the element in a sorted array, which is also a leetcode problem. We have also seen how we can reduce time complexity from O(n) to O(log(n)) with the help of binary search.