Dada una array no ordenada arr[] y un elemento x, encuentre el piso y el techo de x en arr[0..n-1].
El piso de x es el elemento más grande que es menor o igual que x. El piso de x no existe si x es más pequeño que el elemento más pequeño de arr[].
El techo de x es el elemento más pequeño que es mayor o igual que x. El techo de x no existe si x es mayor que el elemento mayor de arr[].
Ejemplos:
Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6} x = 7 Output : Floor = 6 Ceiling = 8 Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6} x = 6 Output : Floor = 6 Ceiling = 6 Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6} x = 10 Output : Floor = 9 Ceiling doesn't exist.
Método 1 (Uso de clasificación):
- Ordenar array de entrada.
- Use la búsqueda binaria para encontrar el piso y el techo de x. Consulte this y this para la implementación de suelo y techo en una array ordenada.
Complejidad de tiempo: O(n log n)
Espacio auxiliar: O(1)
Esta solución funciona bien si hay múltiples consultas de piso y techo en una array estática. Podemos ordenar la array una vez y responder las consultas en tiempo O (Log n).
Método 2 (Usar búsqueda lineal:
La idea es atravesar una array y realizar un seguimiento de dos distancias con respecto a x.
- Distancia mínima del elemento mayor o igual a x.
- Distancia mínima del elemento menor o igual a x.
Finalmente imprima elementos con distancias mínimas.
C++
// C++ program to find floor and ceiling in an // unsorted array. #include<bits/stdc++.h> using namespace std; // Function to floor and ceiling of x in arr[] void floorAndCeil(int arr[], int n, int x) { // Indexes of floor and ceiling int fInd, cInd; // Distances of current floor and ceiling int fDist = INT_MAX, cDist = INT_MAX; for (int i=0; i<n; i++) { // If current element is closer than // previous ceiling. if (arr[i] >= x && cDist > (arr[i] - x)) { cInd = i; cDist = arr[i] - x; } // If current element is closer than // previous floor. if (arr[i] <= x && fDist > (x - arr[i])) { fInd = i; fDist = x - arr[i]; } } if (fDist == INT_MAX) cout << "Floor doesn't exist " << endl; else cout << "Floor is " << arr[fInd] << endl; if (cDist == INT_MAX) cout << "Ceil doesn't exist " << endl; else cout << "Ceil is " << arr[cInd] << endl; } // Driver code int main() { int arr[] = {5, 6, 8, 9, 6, 5, 5, 6}; int n = sizeof(arr)/sizeof(int); int x = 7; floorAndCeil(arr, n, x); return 0; }
Java
// Java program to find floor and ceiling in an // unsorted array. import java.io.*; class GFG { // Function to floor and ceiling of x in arr[] public static void floorAndCeil(int arr[], int x) { int n = arr.length; // Indexes of floor and ceiling int fInd = -1, cInd = -1; // Distances of current floor and ceiling int fDist = Integer.MAX_VALUE, cDist = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // If current element is closer than // previous ceiling. if (arr[i] >= x && cDist > (arr[i] - x)) { cInd = i; cDist = arr[i] - x; } // If current element is closer than // previous floor. if (arr[i] <= x && fDist > (x - arr[i])) { fInd = i; fDist = x - arr[i]; } } if(fDist == Integer.MAX_VALUE) System.out.println("Floor doesn't exist " ); else System.out.println("Floor is " + arr[fInd]); if(cDist == Integer.MAX_VALUE) System.out.println("Ceil doesn't exist "); else System.out.println("Ceil is " + arr[cInd]); } public static void main (String[] args) { int arr[] = {5, 6, 8, 9, 6, 5, 5, 6}; int x = 7; floorAndCeil(arr, x); } }
Python 3
# Python 3 program to find # floor and ceiling in an # unsorted array. import sys # Function to floor and # ceiling of x in arr[] def floorAndCeil(arr, n, x): # Distances of current # floor and ceiling fDist = sys.maxsize cDist = sys.maxsize for i in range(n): # If current element is closer # than previous ceiling. if (arr[i] >= x and cDist > (arr[i] - x)): cInd = i cDist = arr[i] - x # If current element is closer # than previous floor. if (arr[i] <= x and fDist > (x - arr[i])): fInd = i fDist = x - arr[i] if (fDist == sys.maxsize): print("Floor doesn't exist ") else: print("Floor is " + str(arr[fInd])) if (cDist == sys.maxsize): print( "Ceil doesn't exist ") else: print("Ceil is " + str(arr[cInd])) # Driver code if __name__ == "__main__": arr = [5, 6, 8, 9, 6, 5, 5, 6] n = len(arr) x = 7 floorAndCeil(arr, n, x) # This code is contributed # by ChitraNayal
C#
// C# program to find floor and ceiling in an // unsorted array. using System; class GFG { // Function to floor and ceiling of x in arr[] public static void floorAndCeil(int []arr, int x) { int n = arr.Length; // Indexes of floor and ceiling int fInd = -1, cInd = -1; // Distances of current floor and ceiling int fDist = int.MaxValue, cDist =int.MaxValue; for (int i = 0; i < n; i++) { // If current element is closer than // previous ceiling. if (arr[i] >= x && cDist > (arr[i] - x)) { cInd = i; cDist = arr[i] - x; } // If current element is closer than // previous floor. if (arr[i] <= x && fDist > (x - arr[i])) { fInd = i; fDist = x - arr[i]; } } if(fDist == int.MaxValue) Console.Write("Floor doesn't exist " ); else Console.WriteLine("Floor is " + arr[fInd]); if(cDist == int.MaxValue) Console.Write("Ceil doesn't exist "); else Console.Write("Ceil is " + arr[cInd]); } // Driver code public static void Main () { int []arr = {5, 6, 8, 9, 6, 5, 5, 6}; int x = 7; floorAndCeil(arr, x); } } // This code is contributed by nitin mittal.
PHP
<?php // PHP program to find // floor and ceiling in // an unsorted array. // Function to floor and // ceiling of x in arr[] function floorAndCeil($arr, $n, $x) { // Indexes of floor // and ceiling $fInd = 0; $cInd = 0; // Distances of current // floor and ceiling $fDist = 999999; $cDist = 999999; for ($i = 0; $i < $n; $i++) { // If current element // is closer than // previous ceiling. if ($arr[$i] >= $x && $cDist > ($arr[$i] - $x)) { $cInd = $i; $cDist = $arr[$i] - $x; } // If current element // is closer than // previous floor. if ($arr[$i] <= $x && $fDist > ($x - $arr[$i])) { $fInd = $i; $fDist = $x - $arr[$i]; } } if ($fDist == 999999) echo "Floor doesn't ". "exist " . "\n" ; else echo "Floor is " . $arr[$fInd] . "\n"; if ($cDist == 999999) echo "Ceil doesn't " . "exist " . "\n"; else echo "Ceil is " . $arr[$cInd] . "\n"; } // Driver code $arr = array(5, 6, 8, 9, 6, 5, 5, 6); $n = count($arr); $x = 7; floorAndCeil($arr, $n, $x); // This code is contributed // by Sam007 ?>
Javascript
<script> // Javascript program to find floor and ceiling in an // unsorted array. // Function to floor and ceiling of x in arr[] function floorAndCeil(arr,x) { let n = arr.length; // Indexes of floor and ceiling let fInd = -1, cInd = -1; // Distances of current floor and ceiling let fDist = Number.MAX_VALUE, cDist = Number.MAX_VALUE; for (let i = 0; i < n; i++) { // If current element is closer than // previous ceiling. if (arr[i] >= x && cDist > (arr[i] - x)) { cInd = i; cDist = arr[i] - x; } // If current element is closer than // previous floor. if (arr[i] <= x && fDist > (x - arr[i])) { fInd = i; fDist = x - arr[i]; } } if(fDist == Number.MAX_VALUE) document.write("Floor doesn't exist <br>" ); else document.write("Floor is " + arr[fInd]+"<br>"); if(cDist == Number.MAX_VALUE) document.write("Ceil doesn't exist <br>"); else document.write("Ceil is " + arr[cInd]+"<br>"); } let arr=[5, 6, 8, 9, 6, 5, 5, 6]; let x = 7; floorAndCeil(arr, x); // This code is contributed by rag2127 </script>
Floor is 6 Ceil is 8
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Artículos relacionados :
Techo en un arreglo ordenado
Piso en un arreglo ordenado
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