Find first and last positions of an element in a sorted array in C++

January 12, 2022

First and last positions of an element in a sorted array in C++

 

Here, in this page we will discuss the program to find the first and last positions of an element in a sorted array in C++ Programming language. We are given with an array in which elements are sorted in increasing order, and we need to print the first and last positions of an element say x. We will discuss linear search algorithm and binary search algorithm both. 

Example :

  • Input : arr[5] = { 1, 1, 2, 2, 3} and x = 2
  • Output : First Position is 2
                    Last Position is 3
First and last positions of an element in a sorted array in C++

Method 1 (Using Linear Search):

 

  • Take two variable say first and last to hold the first and last position and initialize them with -1, i.e, first = -1 and last = -1.
  • Now, run a loop from 0 to n,
  • If i-th element is equal to x and first == -1, then update first = i and last = i.
  • Else if i-th element is equal to x, then update last = i.
  • After complete iteration
  • Check if first == -1 then print “NOT FOUND”
  • Else print first and last values respectively.

 

Time and Space Complexity :

  • Time Complexity : O(n)
  • Space Complexity : O(1)
Find Fist and last position

Code to find first and last positions of an element in a sorted array in C++

#include<bits/stdc++.h>
using namespace std;

int main(){

     int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
     int n = sizeof(arr) / sizeof(int);
     int x = 2;

     int first=-1, last=-1;

     for(int i=0; i<n; i++){

      if(arr[i]==x and first==-1){
         first = i;
         last = i;
      }

      else if (arr[i]==x)
         last = i;
    }

    if(first == -1)
    cout<<"NOT FOUND";
    else
    cout<<"First position is : "<<first<<"\nLast position is : "<<last;
}
Output :

First position is 1 
Last position is 4

Method 2 (Using Binary Search):

  • Take two variable say first and last to hold the first and last position and initialize them with -1, i.e, first = -1 and last = -1.
  • Declare three variables low=0, high=n-1 and mid.
  • Now, let’s find the first position,
  • For this run a while loop that will terminate if low>=high,
  • Inside loop find mid,  mid=low+((high-low)/2)
  • Check if arr[mid] < x, then set low = mid+1.
  • Otherwise set, high = mid.
  • After termination of while loop check if arr[low]==x, then set first = low, otherwise print “NOT FOUND” and return.
  • Now, let’s find the last position,
  • For this run a while loop that will terminate if low>=high,
  • Inside loop find mid,  mid=low+((high-low+1)/2)
  • Check if arr[mid] > x, then set high = mid-1.
  • Otherwise set, low = mid.
  • After termination of while loop check if arr[low]==x, then set last = low
  • Print the value of first and last.

 

Time and Space Complexity :

  • Time Complexity : O(logn)
  • Space Complexity : O(1)

Code to find first and last positions of an element in a sorted array in C++

#include<bits/stdc++.h>
using namespace std;

int main(){

     int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
     int n = sizeof(arr) / sizeof(int);
     int x = 2;

     int first=-1, last=-1;
     int low=0, high=n-1, mid;

     //For finding first position
     while(low<high){
        mid = low+(high-low)/2;
        if(arr[mid]<x)
          low=mid+1;
        else high=mid;
     }

     if(arr[low] != x){
        cout<<"NOT FOUND";
        return 0;
     }

     first = low;
     low=0;
     high = n-1;

     //for finding last position
     while(low<high){
        mid = low+(high-low+1)/2;
        if(arr[mid]>x)
           high=mid-1;
        else low=mid;
     }

    if(arr[low] == x){
       last = low; 
    }
   cout<<"First position is : "<<first<<"\nLast position is : "<<last;
}
Output :

First position is 1 
Last position is 4
Software Engineering SDLC