An efficient approach using binary search
1. For the first occurrence of a number
a) If (high >= low)
b) Calculate mid = low + (high – low)/2;
c) If ((mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
d) Else if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
e) Else
return first(arr, low, (mid -1), x, n);
f) Otherwise return -1;
2. For the last occurrence of a number
a) if (high >= low)
b) calculate mid = low + (high – low)/2;
c)if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
d) else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
e) else
return last(arr, (mid + 1), high, x, n);
f) otherwise return -1;
Below is the implementation of the above approach:
C++
// C++ program to find first and last occurrences of // a number in a given sorted array #include <bits/stdc++.h> using namespace std; /* if x is present in arr[] then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */ int first( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) return mid; else if (x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid - 1), x, n); } return -1; } /* if x is present in arr[] then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */ int last( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) return mid; else if (x < arr[mid]) return last(arr, low, (mid - 1), x, n); else return last(arr, (mid + 1), high, x, n); } return -1; } // Driver program int main() { int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = sizeof (arr) / sizeof ( int ); int x = 8; printf ( "First Occurrence = %d\t" , first(arr, 0, n - 1, x, n)); printf ( "\nLast Occurrence = %d\n" , last(arr, 0, n - 1, x, n)); return 0; } // This code is contributed by Sania Kumari Gupta // (kriSania804) |
C
// C program to find first and last occurrences of // a number in a given sorted array #include <stdio.h> /* if x is present in arr[] then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */ int first( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) return mid; else if (x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid - 1), x, n); } return -1; } /* if x is present in arr[] then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */ int last( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) return mid; else if (x < arr[mid]) return last(arr, low, (mid - 1), x, n); else return last(arr, (mid + 1), high, x, n); } return -1; } // Driver program int main() { int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = sizeof (arr) / sizeof ( int ); int x = 8; printf ( "First Occurrence = %d\t" , first(arr, 0, n - 1, x, n)); printf ( "\nLast Occurrence = %d\n" , last(arr, 0, n - 1, x, n)); return 0; } // This code is contributed by Sania Kumari Gupta // (kriSania804) |
Java
// Java program to find first and last occurrence of // an elements in given sorted array import java.io.*; class GFG { /* if x is present in arr[] then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */ public static int first( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2 ; if ((mid == 0 || x > arr[mid - 1 ]) && arr[mid] == x) return mid; else if (x > arr[mid]) return first(arr, (mid + 1 ), high, x, n); else return first(arr, low, (mid - 1 ), x, n); } return - 1 ; } /* if x is present in arr[] then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */ public static int last( int arr[], int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2 ; if ((mid == n - 1 || x < arr[mid + 1 ]) && arr[mid] == x) return mid; else if (x < arr[mid]) return last(arr, low, (mid - 1 ), x, n); else return last(arr, (mid + 1 ), high, x, n); } return - 1 ; } 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 ; System.out.println( "First Occurrence = " + first(arr, 0 , n - 1 , x, n)); System.out.println( "Last Occurrence = " + last(arr, 0 , n - 1 , x, n)); } } |
Python3
# Python 3 program to find first and # last occurrences of a number in # a given sorted array # if x is present in arr[] then # returns the index of FIRST # occurrence of x in arr[0..n-1], # otherwise returns -1 def first(arr, low, high, x, n): if (high > = low): mid = low + (high - low) / / 2 if ((mid = = 0 or x > arr[mid - 1 ]) and arr[mid] = = x): return mid elif (x > arr[mid]): return first(arr, (mid + 1 ), high, x, n) else : return first(arr, low, (mid - 1 ), x, n) return - 1 # if x is present in arr[] then # returns the index of LAST occurrence # of x in arr[0..n-1], otherwise # returns -1 def last(arr, low, high, x, n): if (high > = low): mid = low + (high - low) / / 2 if ((mid = = n - 1 or x < arr[mid + 1 ]) and arr[mid] = = x): return mid elif (x < arr[mid]): return last(arr, low, (mid - 1 ), x, n) else : return last(arr, (mid + 1 ), high, x, n) return - 1 # 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 Nikita Tiwari. |
C#
// C# program to find first and last occurrence // of an elements in given sorted array using System; class GFG { /* if x is present in arr[] then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */ public static int first( int [] arr, int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) return mid; else if (x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid - 1), x, n); } return -1; } /* if x is present in arr[] then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */ public static int last( int [] arr, int low, int high, int x, int n) { if (high >= low) { int mid = low + (high - low) / 2; if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) return mid; else if (x < arr[mid]) return last(arr, low, (mid - 1), x, n); else return last(arr, (mid + 1), high, x, n); } return -1; } // Driver code public static void Main() { int [] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 }; int n = arr.Length; int x = 8; Console.WriteLine( "First Occurrence = " + first(arr, 0, n - 1, x, n)); Console.Write( "Last Occurrence = " + last(arr, 0, n - 1, x, n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find first // and last occurrences of a // number in a given sorted array // if x is present in arr[] then // returns the index of FIRST // occurrence of x in arr[0..n-1], // otherwise returns -1 function first( $arr , $low , $high , $x , $n ) { if ( $high >= $low ) { $mid = floor ( $low + ( $high - $low ) / 2); if (( $mid == 0 or $x > $arr [ $mid - 1]) and $arr [ $mid ] == $x ) return $mid ; else if ( $x > $arr [ $mid ]) return first( $arr , ( $mid + 1), $high , $x , $n ); else return first( $arr , $low , ( $mid - 1), $x , $n ); } return -1; } // if x is present in arr[] // then returns the index of // LAST occurrence of x in // arr[0..n-1], otherwise // returns -1 function last( $arr , $low , $high , $x , $n ) { if ( $high >= $low ) { $mid = floor ( $low + ( $high - $low ) / 2); if (( $mid == $n - 1 or $x < $arr [ $mid + 1]) and $arr [ $mid ] == $x ) return $mid ; else if ( $x < $arr [ $mid ]) return last( $arr , $low , ( $mid - 1), $x , $n ); else return last( $arr , ( $mid + 1), $high , $x , $n ); return -1; } } // Driver Code $arr = array (1, 2, 2, 2, 2, 3, 4, 7, 8, 8); $n = count ( $arr ); $x = 8; echo "First Occurrence = " , first( $arr , 0, $n - 1, $x , $n ), "\n" ; echo "Last Occurrence = " , last( $arr , 0, $n - 1, $x , $n ); // This code is contributed by anuj_67 ?> |
Javascript
<script> // JavaScript program to find first and last occurrences of // a number in a given sorted array /* if x is present in arr then returns the index of FIRST occurrence of x in arr[0..n-1], otherwise returns -1 */ function first(arr,low,high,x,n) { if (high >= low) { let mid = low + Math.floor((high - low) / 2); if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x) return mid; else if (x > arr[mid]) return first(arr, (mid + 1), high, x, n); else return first(arr, low, (mid - 1), x, n); } return -1; } /* if x is present in arr then returns the index of LAST occurrence of x in arr[0..n-1], otherwise returns -1 */ function last(arr, low, high, x, n) { if (high >= low) { let mid = low + Math.floor((high - low) / 2); if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x) return mid; else if (x < arr[mid]) return last(arr, low, (mid - 1), x, n); else return last(arr, (mid + 1), high, x, n); } return -1; } // Driver program let arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ]; let n = arr.length; let x = 8; document.write( "First Occurrence = " + first(arr, 0, n - 1, x, n), "</br>" ); console.log( "Last Occurrence = " + last(arr, 0, n - 1, x, n), "</br>" ); // code is contributed by shinjanpatra </script> |
First Occurrence = 8 Last Occurrence = 9
Time Complexity: O(log n)
Auxiliary Space: O(log n), for recursion call stack
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)