An approach using inbuilt functions
Below is the implementation using an inbuilt function:
C++
#include <bits/stdc++.h> using namespace std; void findFirstAndLast( int arr[], int n, int x) { int first, last; // to store first occurrence first = lower_bound(arr, arr + n, x) - arr; // to store last occurrence last = upper_bound(arr, arr + n, x) - arr - 1; if (first == n) { first = -1; last = -1; } cout << "First Occurrence = " << first << "\nLast Occurrence = " << last; } // Driver code int main() { int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = sizeof (arr) / sizeof ( int ); int x = 8; findFirstAndLast(arr, n, x); return 0; } |
Java
// Java program for the above approach import java.util.ArrayList; public class GFG { public static int first(ArrayList list, int x) { // return first occurrence index // of element x in ArrayList // using method indexOf() return list.indexOf(x); } public static int last(ArrayList list, int x) { // return last occurrence index // of element x in ArrayList // using method lastIndexOf() return list.lastIndexOf(x); } public static void main(String[] args) { int arr[] = { 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 }; ArrayList<Integer> clist = new ArrayList<>(); // adding elements of array to ArrayList for ( int i : arr) clist.add(i); int x = 8 ; // displaying the first occurrence System.out.println( "First Occurrence = " + first(clist, x)); // displaying the last occurrence System.out.println( "Last Occurrence = " + last(clist, x)); } } |
Python
# Python3 program to find first and # last occurrences of a number in a # given sorted array # function to find the first occurrence of the number def first(arr, low, high, key, length): return arr.index(x) # function to find the last occurrence of the number def last(arr, low, high, key, length): return length - 1 - arr[:: - 1 ].index(x) # Driver program arr = [ 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ] n = len (arr) x = 8 print ( 'First Occurrence = ' , first(arr, 0 , n - 1 , x, n)) print ( 'Last Occurrence = ' , last(arr, 0 , n - 1 , x, n)) # This code is contributed by postaarpan |
C#
// Include namespace system using System; using System.Collections.Generic; class GFG { public static int first(List< int > list, int x) { // return first occurrence index // of element x in ArrayList // using method indexOf() return list.IndexOf(x); } public static int last(List< int > list, int x) { // return last occurrence index // of element x in ArrayList // using method lastIndexOf() return list.LastIndexOf(x); } public static void Main() { int [] arr = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; var clist = new List< int >(); // adding elements of array to ArrayList foreach ( int i in arr) { clist.Add(i); } var x = 8; // displaying the first occurrence Console.WriteLine( "First Occurrence = " + GFG.first(clist, x).ToString()); // displaying the last occurrence Console.WriteLine( "Last Occurrence = " + GFG.last(clist, x).ToString()); } } // This code is contributed by aadityaburujwale. |
Javascript
// JavaScript program for the above approach function first(list, x){ // return first occurrence index // of element x in ArrayList // using method indexOf() return list.indexOf(x); } function last(list, x){ // return last occurrence index // of element x in ArrayList // using method lastIndexOf() return list.lastIndexOf(x); } let arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ]; let clist = new Array(); // adding elements of array to ArrayList for (let i=0;i<arr.length;i++){ clist.push(arr[i]); } let x = 8; // displaying the first occurrence console.log( "First Occurrence = " + first(clist, x) + "<br>" ); // displaying the last occurrence console.log( "Last Occurrence = " + last(clist, x)); // This code is contributed by lokeshmvs21. |
First Occurrence = 8 Last Occurrence = 9
Time Complexity: O(n) As Inbuilt function runs a internal for loop for finding the first index and last index of that element so it takes O(n)
Auxiliary Space: O(1)
Another Approach:
- For the first occurrence, we will first find the index of the number and then search again in the left subarray as long as we are finding the number.
- For the last occurrence, we will first find the index of the number and then search again in the right subarray as long as we are finding the number
Follow the steps mentioned below to implement the idea:
- First we create an array ans[] of size 2 to store the first occurrence and last occurrence.Create
- Create a function search(int[] nums, int target, boolean findStartIndex) to find the index value of target.
- And for first occurrence set ans[0] = search(arr, target, true) and last occurrence set ans[1] = search(arr, target, false) and these function do following things:
? Set ans = -1 , start = 0 , end = arr.length – 1 .
? Iterate a loop while start <= end , such as:
? Set mid = start + (end – start) / 2 .
? Check if target < arr[mid] ,then set end = mid – 1.
? Else check if target > arr[mid], then set start = mid – 1.
? Otherwise , set ans = mid and check further such as
? If findStartIndex == true , then set end = mid – 1 .
? Else set start = mid + 1.
? Return ans as the index value of target.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; // if target is present in arr[] then returns // the index of FIRST occurrence and last occurrence // of target in arr[0..n-1], otherwise returns -1 int search( int nums[], int n, int target, bool findStartIndex) { int ans = -1; int start = 0; int end = n - 1; while (start <= end) { // find the middle element // might be possible that (start + end) // exceeds the range of int in C++ int mid = start + (end - start) / 2; if (target < nums[mid]) { end = mid - 1; } else if (target > nums[mid]) { start = mid + 1; } else { // potential ans found ans = mid; if (findStartIndex) { end = mid - 1; } else { start = mid + 1; } } } return ans; } // Driver program int main() { int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int n = sizeof (arr) / sizeof (arr[0]); int x = 8; int ans[] = {-1,-1}; // For first occurrence ans[0] = search(arr,n,x, true ); if (ans[0] != -1){ // For last occurrence ans[1] = search(arr,n,x, false ); } cout << "First Occurrence: " << ans[0] << endl; cout << "Last Occurrence: " << ans[1] << endl; return 0; } |
Java
// Java program to find first // and last occurrences of a // number in a given sorted array import java.util.*; class GFG { // if target is present in arr[] then // returns the index of FIRST // occurrence and last occurrence of target in // arr[0..n-1], otherwise returns -1 static int search( int [] nums, int target, boolean findStartIndex) { int ans = - 1 ; int start = 0 ; int end = nums.length - 1 ; while (start <= end) { // find the middle element // int mid = (start + end) / 2; // might be possible that (start + end) // exceeds the range of int in java int mid = start + (end - start) / 2 ; if (target < nums[mid]) { end = mid - 1 ; } else if (target > nums[mid]) { start = mid + 1 ; } else { // potential ans found ans = mid; if (findStartIndex) { end = mid - 1 ; } else { start = mid + 1 ; } } } return ans; } // Driver program public static void main(String[] args) { int arr[] = { 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 }; int n = arr.length; int x = 8 ; int [] ans = { - 1 , - 1 }; // For first occurrence ans[ 0 ] = search(arr,x, true ); if (ans[ 0 ] != - 1 ) { // For last occurrence ans[ 1 ] = search(arr, x, false ); } System.out.println( "First Occurrence = " + ans[ 0 ]); System.out.println( "Last Occurrence = " + ans[ 1 ]); } } |
C#
using System; public class GFG { // if target is present in nums[] then // returns the index of FIRST // occurrence and last occurrence of target in // nums[0..n-1], otherwise returns -1 static int search( int [] nums, int target, bool findStartIndex) { int ans = -1; int start = 0; int end = nums.Length - 1; while (start <= end) { // find the middle element // int mid = (start + end) / 2; // might be possible that (start + end) // exceeds the range of int in C# int mid = start + (end - start) / 2; if (target < nums[mid]) { end = mid - 1; } else if (target > nums[mid]) { start = mid + 1; } else { // potential ans found ans = mid; if (findStartIndex) { end = mid - 1; } else { start = mid + 1; } } } return ans; } // Driver program public static void Main( string [] args) { int [] nums = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = nums.Length; int target = 8; int [] ans = { -1, -1 }; // For first occurrence ans[0] = search(nums,target, true ); if (ans[0] != -1) { // For last occurrence ans[1] = search(nums, target, false ); } Console.WriteLine( "First Occurrence = " + ans[0]); Console.WriteLine( "Last Occurrence = " + ans[1]); } } |
Python3
# Python program to find first # and last occurrences of a # number in a given sorted array # if target is present in nums[] then # returns the index of FIRST # occurrence and last occurrence of target in # nums[0..n-1], otherwise returns -1 def search(nums, target, findStartIndex): ans = - 1 start = 0 end = len (nums) - 1 while start < = end: # find the middle element mid = start + (end - start) / / 2 if target < nums[mid]: end = mid - 1 elif target > nums[mid]: start = mid + 1 else : # potential ans found ans = mid if findStartIndex: end = mid - 1 else : start = mid + 1 return ans # Driver program arr = [ 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ] n = len (arr) x = 8 ans = [ - 1 , - 1 ] # For first occurrence ans[ 0 ] = search(arr, x, True ) if ans[ 0 ] ! = - 1 : # For last occurrence ans[ 1 ] = search(arr, x, False ) print ( "First Occurrence =" , ans[ 0 ]) print ( "Last Occurrence =" , ans[ 1 ]) |
Javascript
// JavaScript program to find first // and last occurrences of a // number in a given sorted array // if target is present in nums[] then // returns the index of FIRST // occurrence and last occurrence of target in // nums[0..n-1], otherwise returns -1 function search(nums, target, findStartIndex) { let ans = -1; let start = 0; let end = nums.length - 1; while (start <= end) { // find the middle element let mid = Math.floor(start + (end - start) / 2); if (target < nums[mid]) { end = mid - 1; } else if (target > nums[mid]) { start = mid + 1; } else { // potential ans found ans = mid; if (findStartIndex) { end = mid - 1; } else { start = mid + 1; } } } return ans; } // Driver program let arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]; let n = arr.length; let x = 8; let ans = [-1, -1]; // For first occurrence ans[0] = search(arr, x, true ); if (ans[0] != -1) { // For last occurrence ans[1] = search(arr, x, false ); } console.log( "First Occurrence =" , ans[0]); console.log( "Last Occurrence =" , ans[1]); |
First Occurrence: 8 Last Occurrence: 9
Time Complexity: O(log n)
Auxiliary Space: O(1)
Extended Problem : Count number of occurrences in a sorted array
Find first and last positions of an element in a sorted array
Given a sorted array arr[] with possibly duplicate elements, the task is to find indexes of the first and last occurrences of an element x in the given array.
Examples:
Input : arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, x = 5
Output : First Occurrence = 2
Last Occurrence = 5Input : arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }, x = 7
Output : First Occurrence = 6
Last Occurrence = 6
A Naive Approach:
The idea to solve this problem is iterate on the elements of given array and check given elements in an array and keep track of first and last occurrence of the found element’s index.
Below are the steps to implement the above idea:
- Run a for loop and for i = 0 to n-1
- Take first = -1 and last = -1
- When we find an element first time then we update first = i
- We always update last=i whenever we find the element.
- We print first and last.
Below is the implementation of the above approach:
C++
// C++ program to find first and last occurrence of // an elements in given sorted array #include <bits/stdc++.h> using namespace std; // Function for finding first and last occurrence // of an elements void findFirstAndLast( int arr[], int n, int x) { int first = -1, last = -1; for ( int i = 0; i < n; i++) { if (x != arr[i]) continue ; if (first == -1) first = i; last = i; } if (first != -1) cout << "First Occurrence = " << first << "\nLast Occurrence = " << last; else cout << "Not Found" ; } // Driver code int main() { int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = sizeof (arr) / sizeof ( int ); int x = 8; findFirstAndLast(arr, n, x); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to find first and last occurrence of // an elements in given sorted array #include <stdio.h> // Function for finding first and last occurrence // of an elements void findFirstAndLast( int arr[], int n, int x) { int first = -1, last = -1; for ( int i = 0; i < n; i++) { if (x != arr[i]) continue ; if (first == -1) first = i; last = i; } if (first != -1) printf ( "First Occurrence = %d \nLast Occurrence = %d" , first, last); else printf ( "Not Found" ); } // Driver code int main() { int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = sizeof (arr) / sizeof ( int ); int x = 8; findFirstAndLast(arr, n, x); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to find first and last occurrence of // an elements in given sorted array import java.io.*; class GFG { // Function for finding first and last occurrence // of an elements public static void findFirstAndLast( int arr[], int x) { int n = arr.length; int first = - 1 , last = - 1 ; for ( int i = 0 ; i < n; i++) { if (x != arr[i]) continue ; if (first == - 1 ) first = i; last = i; } if (first != - 1 ) { System.out.println( "First Occurrence = " + first); System.out.println( "Last Occurrence = " + last); } else System.out.println( "Not Found" ); } public static void main(String[] args) { int arr[] = { 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 }; int x = 8 ; findFirstAndLast(arr, x); } } // This code is contributed by Aditya Kumar (adityakumar129) |
Python3
# Python 3 program to find first and # last occurrence of an elements in # given sorted array # Function for finding first and last # occurrence of an elements def findFirstAndLast(arr, n, x): first = - 1 last = - 1 for i in range ( 0 , n): if (x ! = arr[i]): continue if (first = = - 1 ): first = i last = i if (first ! = - 1 ): print ( "First Occurrence = " , first, " \nLast Occurrence = " , last) else : print ( "Not Found" ) # Driver code arr = [ 1 , 2 , 2 , 2 , 2 , 3 , 4 , 7 , 8 , 8 ] n = len (arr) x = 8 findFirstAndLast(arr, n, x) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find first and last // occurrence of an elements in given // sorted array using System; class GFG { // Function for finding first and // last occurrence of an elements static void findFirstAndLast( int [] arr, int x) { int n = arr.Length; int first = -1, last = -1; for ( int i = 0; i < n; i++) { if (x != arr[i]) continue ; if (first == -1) first = i; last = i; } if (first != -1) { Console.WriteLine( "First " + "Occurrence = " + first); Console.Write( "Last " + "Occurrence = " + last); } else Console.Write( "Not Found" ); } // Driver code public static void Main() { int [] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int x = 8; findFirstAndLast(arr, x); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find first and last // occurrence of an elements in given // sorted array // Function for finding first and last // occurrence of an elements function findFirstAndLast( $arr , $n , $x ) { $first = -1; $last = -1; for ( $i = 0; $i < $n ; $i ++) { if ( $x != $arr [ $i ]) continue ; if ( $first == -1) $first = $i ; $last = $i ; } if ( $first != -1) echo "First Occurrence = " , $first , "\n" , "\nLast Occurrence = " , $last ; else echo "Not Found" ; } // Driver code $arr = array (1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ); $n = count ( $arr ); $x = 8; findFirstAndLast( $arr , $n , $x ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find first and last occurrence of // an elements in given sorted array // Function for finding first and last occurrence // of an elements function findFirstAndLast(arr,x) { let n = arr.length; let first = -1, last = -1; for (let i = 0; i < n; i++) { if (x != arr[i]) continue ; if (first == -1) first = i; last = i; } if (first != -1) { document.write( "First Occurrence = " + first + "<br>" ); document.write( "Last Occurrence = " + last + "<br>" ); } else document.write( "Not Found" ); } let arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ]; let x = 8; findFirstAndLast(arr, x); // This code is contributed by avanitrachhadiya2155 </script> |
First Occurrence = 8 Last Occurrence = 9
Time Complexity: O(n)
Auxiliary Space: O(1)