Trouver la valeur ceil et floor d'un élément dans un tableau trié donné
Dans ce didacticiel, nous allons apprendre à trouver la valeur plafond et plancher d'un élément dans un tableau trié donné. Mais avant d'aller plus loin, si vous n'êtes pas familier avec les concepts du tableau, alors consultez l'article Tableaux en Java.
Saisie :
Tableau :15 17 18 19 20 21 22 24 25 26 27
Élément :16
Sortie :
Étage :15
Plafond :17
Le problème ci-dessus peut être résolu de deux manières :
Méthode 1 :Recherche binaire
Méthode 2 :Recherche linéaire
Examinons chacune de ces méthodes séparément.
Programme 1 :Pour trouver la valeur Ceil et Floor d'un élément dans un tableau trié donné
Dans cette approche, nous effectuons simplement une recherche binaire pour trouver la valeur plancher et plafond d'un élément dans un tableau trié donné.
Algorithme
- Démarrer
- Déclarez une taille de tableau.
- Demandez à l'utilisateur d'initialiser la taille du tableau.
- Déclarez un tableau.
- Demandez à l'utilisateur d'initialiser le tableau.
- Déclarez une variable pour stocker la valeur de l'élément à rechercher.
- Appelez une méthode pour vérifier la valeur ceil.
- Initialisez le plafond à -1, puis parcourez les éléments pour rechercher la valeur du plafond.
- Dans la méthode ceil, si x est égal à l'élément du milieu, alors c'est la valeur ceil.
- Si x est inférieur à l'élément du milieu, alors la valeur ceil se situe dans le sous-tableau de gauche. Mettez à jour la valeur ceil et recherchez-la à nouveau dans A[low,mid-1].
- Si x est supérieur à l'élément du milieu, alors la valeur ceil se situe dans le sous-tableau de droite. Mettez à jour la valeur ceil et recherchez-la à nouveau dans A[mid,end]. Renvoyez la valeur ceil trouvée.
- Appelez une méthode pour vérifier la valeur plancher.
- Initialisez le plancher à -1, puis parcourez les éléments pour rechercher la valeur plancher.
- Dans la méthode floor, si x est égal à l'élément du milieu, alors c'est la valeur floor.
- Si x est inférieur à l'élément du milieu, alors la valeur plancher se situe dans le sous-tableau de gauche. Mettez à jour la valeur plancher et recherchez-la à nouveau dans A[low,mid-1].
- Si x est supérieur à l'élément du milieu, alors la valeur plancher se situe dans le sous-tableau de droite. Mettez à jour la valeur plancher et recherchez-la à nouveau dans A[moyen,élevé].
- Renvoyer la valeur plancher trouvée.
- Afficher à la fois la valeur plafond et la valeur plancher.
- Arrêter
Vous trouverez ci-dessous le code correspondant.
Le programme ci-dessous montre comment trouver la valeur ceil et floor d'un élément dans un tableau trié donné
// Java Program to find the ceil and floor of an element in an array
import java.io.*;
import java.util.Scanner;
public class Main
{
public static void main(String[] args)
{
//Take input from the user
Scanner sc=new Scanner(System.in);
int n; //Declare size of an array
System.out.println("Enter the size of the array: ");
n=sc.nextInt(); //Initialize the array size
int arr[]=new int[n]; //Declare an array
System.out.println("Enter the array elements: ");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt(); //Initialize the array elements
}
//Enter the element whose floor and ceil values you want to check
int x;
System.out.println("Enter the element whose floor and ceil values you want to check: ");
x=sc.nextInt();
//Method to check for Ceil
int ceil=getCeil(arr,x);
//Print the Ceil value
System.out.println("Ceil value is "+ceil);
//Method to check for Floor
int floor=getFloor(arr,x);
//Print the floor Value
System.out.println("floor value is "+floor);
}
// Function to find the ceil of X in a sorted array A[],i.e., the smallest integer greater than or equal to X
public static int getCeil(int[] A, int x)
{
// search space is A[left…right]
int left = 0, right = A.length - 1;
// initialize ceil to -1
int ceil = -1;
// loop till the search space is exhausted
while (left <= right)
{
// find the mid-value in the search space
int mid = (left + right) / 2;
// if X is equal to the middle element, it is the ceil
if (A[mid] == x) {
return A[mid];
}
// if X is less than the middle element, the ceil exists in the subarray A[left…mid]; update ceil to the middle element and reduce our search space to the left subarray A[left…mid-1]
else if (x < A[mid])
{
ceil = A[mid];
right = mid - 1;
}
// if X is more than the middle element, the ceil exists in the right subarray A[mid+1…right]
else
{
left = mid + 1;
}
}
return ceil;
}
// Function to find the floor of X in a sorted array A[], i.e., the largest integer less than or equal to X
public static int getFloor(int[] A, int x)
{
int left = 0, right = A.length - 1;
// initialize floor to -1
int floor = -1;
// loop till the search space is exhausted
while (left <= right)
{
// find the mid-value in the search space
int mid = (left + right) / 2;
// if X is equal to the middle element, it is the floor
if (A[mid] == x)
{
return A[mid];
}
// if X is less than the middle element, the floor exists in the left subarray A[left…mid-1]
else if (x < A[mid]) {
right = mid - 1;
}
// if X is more than the middle element, the floor exists in the subarray A[mid…right]; update floor to the middle element and reduce our search space to the right subarray A[mid+1…right]
else {
floor = A[mid];
left = mid + 1;
}
}
return floor;
}
}
Saisissez la taille du tableau :10
Saisissez les éléments du tableau :1 2 3 4 6 7 8 9 10 11
Saisissez l'élément dont vous souhaitez vérifier les valeurs de plancher et de plafond :5
La valeur plafond est de 6
la valeur plancher est de 4
Programme 2 :Pour trouver la valeur Ceil et Floor d'un élément dans un tableau trié donné
Dans cette approche, nous effectuons simplement une recherche linéaire pour trouver la valeur plancher et plafond d'un élément dans un tableau trié donné.
Algorithme
- Démarrer
- Déclarez un tableau trié.
- Déclarez une variable pour stocker la longueur du tableau trié.
- Entrez le nombre dont vous souhaitez vérifier la valeur plancher et plafond.
- Pour trouver la valeur plancher, parcourez le tableau.
- Si l'élément actuel est supérieur à l'élément saisi, imprimez le nombre précédent et rompez la boucle.
- S'il n'y a pas de nombre supérieur à l'élément saisi, imprimez le dernier élément
- Si le premier nombre est supérieur à l'élément saisi, imprimez -1.
- De même, si l'élément saisi est inférieur ou égal au premier élément du tableau, renvoie 0.
- Sinon, parcourez le tableau pour trouver un nombre inférieur au nombre saisi.
- Si aucun élément de ce type n'est trouvé, alors renvoie -1.
- Afficher les deux résultats.
- Arrêtez.
Ci-dessous le code pour le même
/*Java Program to check for Ceil and Floor value*/
public class Main
{
//Check For Ceil Value
static int ceilSearch(int arr[], int low, int high, int x)
{
int i;
if(x <= arr[low])
return low;
for(i = low; i < high; i++)
{
if(arr[i] == x)
return i;
if(arr[i] < x && arr[i+1] >= x)
return i+1;
}
return -1;
}
//Check for floor value
static int floorSearch(int arr[], int n, int x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
// Driver program
public static void main (String[] args)
{
int arr[] = {1, 2, 3 , 4, 7, 8, 9, 10};
int n = arr.length;
int x = 11;
int ceil = ceilSearch(arr, 0, n-1, x);
if(ceil == -1)
System.out.println("Ceiling of "+x +" doesn't exist in array");
else
System.out.println("ceiling of "+x+" is "+arr[ceil]);
int floor = floorSearch(arr, n - 1, x);
if (floor == -1)
System.out.print( "Floor of " + x + " doesn't exist in array ");
else
System.out.print("Floor of " + x + " is " + arr[floor]);
}
}
Le plafond de 11 n'existe pas dans le tableau
Le plancher de 11 est 9
