Dada una array ordenada con elementos posiblemente duplicados, la tarea es encontrar índices de la primera y última aparición de un elemento x en la array dada.
Ejemplos:
Input : arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125} x = 5 Output : First Occurrence = 2 Last Occurrence = 5 Input : arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 } x = 7 Output : First Occurrence = 6 Last Occurrence = 6
El enfoque ingenuo consiste en ejecutar un bucle for y verificar los elementos dados en una array.
1. Run a for loop and for i = 0 to n-1 2. Take first = -1 and last = -1 3. When we find element first time then we update first = i 4. We always update last=i whenever we find the element. 5. We print first and last.
Implementación:
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
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Una solución eficiente a este problema es utilizar una búsqueda binaria.
1. Para la primera aparición de un número
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. Por la última ocurrencia de un número
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;
Implementación:
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
Complejidad de tiempo : O(log n)
Espacio auxiliar : O(Log n)
Implementación iterativa de la solución de búsqueda binaria:
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 x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the left // half. else { res = mid; high = mid - 1; } } return res; } /* 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 x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the right // half. else { res = mid; low = mid + 1; } } return res; } // 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; cout <<"First Occurrence = " << first(arr, x, n); cout <<"\nLast Occurrence = "<< last(arr, x, n); return 0; } // This code is contributed by shivanisinghss2110
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 x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the left // half. else { res = mid; high = mid - 1; } } return res; } /* 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 x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the right // half. else { res = mid; low = mid + 1; } } return res; } // 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, x, n)); printf("\nLast Occurrence = %d\n", last(arr, x, n)); 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 x is present in arr[] then // returns the index of FIRST // occurrence of x in arr[0..n-1], // otherwise returns -1 static int first(int arr[], int x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as // x, we update res and // move to the left half. else { res = mid; high = mid - 1; } } return res; } // If x is present in arr[] then returns // the index of LAST occurrence of x in // arr[0..n-1], otherwise returns -1 static int last(int arr[], int x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, // we update res and move to // the right half. else { res = mid; low = mid + 1; } } return res; } // 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; System.out.println("First Occurrence = " + first(arr, x, n)); System.out.println("Last Occurrence = " + last(arr, x, n)); } } // This code is contributed by Chitranayal
Python3
# Python3 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, x, n): low = 0 high = n - 1 res = -1 while (low <= high): # Normal Binary Search Logic mid = (low + high) // 2 if arr[mid] > x: high = mid - 1 elif arr[mid] < x: low = mid + 1 # If arr[mid] is same as x, we # update res and move to the left # half. else: res = mid high = mid - 1 return res # If x is present in arr[] then returns # the index of FIRST occurrence of x in # arr[0..n-1], otherwise returns -1 def last(arr, x, n): low = 0 high = n - 1 res = -1 while(low <= high): # Normal Binary Search Logic mid = (low + high) // 2 if arr[mid] > x: high = mid - 1 elif arr[mid] < x: low = mid + 1 # If arr[mid] is same as x, we # update res and move to the Right # half. else: res = mid low = mid + 1 return res # Driver code arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ] n = len(arr) x = 8 print("First Occurrence =", first(arr, x, n)) print("Last Occurrence =", last(arr, x, n)) # This code is contributed by Ediga_Manisha.
C#
// C# program to find first // and last occurrences of a // number in a 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 static int first(int []arr, int x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as // x, we update res and // move to the left half. else { res = mid; high = mid - 1; } } return res; } // If x is present in []arr then returns // the index of LAST occurrence of x in // arr[0..n-1], otherwise returns -1 static int last(int []arr, int x, int n) { int low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic int mid = (low + high) / 2; if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, // we update res and move to // the right half. else { res = mid; low = mid + 1; } } return res; } // 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; Console.WriteLine("First Occurrence = " + first(arr, x, n)); Console.WriteLine("Last Occurrence = " + last(arr, x, n)); } } // This code is contributed by 29AjayKumar
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, x, n) { let low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic let mid = Math.floor((low + high) / 2); if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the left // half. else { res = mid; high = mid - 1; } } return res; } /* 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, x, n) { let low = 0, high = n - 1, res = -1; while (low <= high) { // Normal Binary Search Logic let mid = Math.floor((low + high) / 2); if (arr[mid] > x) high = mid - 1; else if (arr[mid] < x) low = mid + 1; // If arr[mid] is same as x, we // update res and move to the right // half. else { res = mid; low = mid + 1; } } return res; } // Driver code 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, x, n),"</br>"); document.write("Last Occurrence = " + last(arr, x, n)); // This code is contributed by shinjanpatra </script>
First Occurrence = 8 Last Occurrence = 9
Tiempo Complejidad : O(log n)
Espacio Auxiliar : O(1)
Usando ArrayList
Agregue todos los elementos de la array a ArrayList y usando el método indexOf() y lastIndexOf() encontraremos la primera posición y la última posición del elemento en la array.
Implementación:
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)); } }
First Occurrence = 8 Last Occurrence = 9
Otro enfoque que utiliza las funciones STL de c ++ límite inferior y superior
Implementación:
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; }
First Occurrence = 8 Last Occurrence = 9
Tiempo Complejidad : O(log n)
Espacio Auxiliar : O(1)
Otro enfoque es usar la función «índice()» de Python3, que busca un elemento dado en la Lista dada y devuelve el índice de su primera aparición en la lista. Usando la función “index( )”, encontramos la Primera Ocurrencia, y usando la función “index( )” en la Lista invertida, encontramos la Última Ocurrencia.
Implementación:
Java
// Java program to find first and // last occurrences of a number in a // given sorted array import java.io.*; import java.util.*; class GFG { // If x is present in arr[] then // returns the index of FIRST & LAST // occurrence of x in arr[0..n-1], // otherwise returns -1 public static void first_last(ArrayList<Integer> arr, int x) { int first = arr.indexOf(x); Collections.reverse(arr); int last = arr.size() - 1 - arr.indexOf(x); System.out.println("First Occurrence = " + first); System.out.println("Last Occurrence = " + last); } public static void main (String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>(10); // using add() to initialize dice values arr.add(1); arr.add(2); arr.add(2); arr.add(2); arr.add(2); arr.add(3); arr.add(4); arr.add(7); arr.add(8); arr.add(8); int x = 8; first_last(arr, x); } } // This code is contributed by kothavvsaakash
Python3
# Python3 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 & LAST # occurrence of x in arr[0..n-1], # otherwise returns -1 def first_last(arr, x): first = arr.index(x) last = len(arr) - 1 - arr[::-1].index(x) print("First Occurrence =", first) print("Last Occurrence =", last) # Driver code arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ] x = 8 first_last(arr, x); # This code is contributed by kothavvsaakash
First Occurrence = 8 Last Occurrence = 9
Problema extendido: cuente el número de ocurrencias en una array ordenada
Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA