Vind de ceil en floor waarde van een element in een bepaalde gesorteerde array
In deze zelfstudie leren we hoe we de plafond- en vloerwaarde van een element in een bepaalde gesorteerde array kunnen vinden. Maar voordat u verder gaat, als u niet bekend bent met de concepten van de array, raadpleeg dan het artikel Arrays in Java.
Invoer:
Reeks:15 17 18 19 20 21 22 24 25 26 27
Element:16
Uitvoer:
Verdieping:15
Plafond:17
Het bovenstaande probleem kan op twee manieren worden opgelost:
Methode 1:Binair zoeken
Methode 2:Lineair zoeken
Laten we elk van deze methoden afzonderlijk bekijken.
Programma 1:Om de plafond- en vloerwaarde van een element in een bepaalde gesorteerde array te vinden
In deze benadering voeren we eenvoudig een binaire zoekopdracht uit om de minimum- en plafondwaarde van een element in een bepaalde gesorteerde array te vinden.
Algoritme
- Begin
- Declareer een arraygrootte.
- Vraag de gebruiker om de arraygrootte te initialiseren.
- Declareer een array.
- Vraag de gebruiker om de array te initialiseren.
- Declareer een variabele om de waarde van het te doorzoeken element op te slaan.
- Bel een methode aan om de plafondwaarde te controleren.
- Initialiseer de ceil op -1 en herhaal de elementen om de ceil-waarde te zoeken.
- In de ceil-methode, als x gelijk is aan het middelste element, dan is dit de ceil-waarde.
- Als x kleiner is dan het middelste element, ligt de ceil-waarde in de linker subarray. Werk de plafondwaarde bij en zoek er opnieuw naar in de A[low,mid-1].
- Als x groter is dan het middelste element, ligt de ceil-waarde in de rechter subarray. Werk de plafondwaarde bij en zoek er opnieuw naar in de A[mid,end].Retourneer de gevonden plafondwaarde.
- Bel een methode aan om de minimumwaarde te controleren.
- Initialiseer de vloer naar -1 en herhaal de elementen om de vloerwaarde te zoeken.
- In de floor-methode, als x gelijk is aan het middelste element, dan is dit de floor-waarde.
- Als x kleiner is dan het middelste element, ligt de vloerwaarde in de linker subarray. Werk de minimumwaarde bij en zoek er opnieuw naar in de A[low,mid-1].
- Als x groter is dan het middelste element, ligt de vloerwaarde in de rechter subarray. Werk de bodemwaarde bij en zoek deze opnieuw in de A[mid,high].
- Retourneer de gevonden minimumwaarde.
- Geef zowel de plafond- als de vloerwaarde weer.
- Stop
Hieronder staat de code voor hetzelfde.
Het onderstaande programma laat zien hoe je de plafond- en vloerwaarde van een element in een gegeven gesorteerde array kunt vinden
// 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;
}
}
Vul de grootte van de array in:10
Voer de array-elementen in:1 2 3 4 6 7 8 9 10 11
Voer het element in waarvan je de vloer- en plafondwaarden wilt controleren:5
Plafondwaarde is 6
bodemwaarde is 4
Programma 2:De plafond- en vloerwaarde van een element in een bepaalde gesorteerde array vinden
In deze benadering voeren we eenvoudigweg een lineaire zoekopdracht uit om de vloer- en plafondwaarde van een element in een bepaalde gesorteerde array te vinden.
Algoritme
- Begin
- Declareer een gesorteerde array.
- Declareer een variabele om de lengte van de gesorteerde array op te slaan.
- Voer het nummer in waarvan u de vloer- en plafondwaarde wilt controleren.
- Om de vloerwaarde te vinden, gaat u door de array.
- Als het huidige element groter is dan het ingevoerde element, druk dan het vorige nummer af en verbreek de lus.
- Als er geen getal groter is dan het ingevoerde element, druk dan het laatste element af
- Als het eerste getal groter is dan het ingevoerde element, druk dan -1 af.
- Op dezelfde manier, als het ingevoerde element kleiner is dan of gelijk is aan het eerste element in de array, retourneert u 0.
- Anders doorloop je de array om een getal te vinden dat kleiner is dan het ingevoerde getal.
- Als zo'n element niet wordt gevonden, retourneer dan -1.
- Beide resultaten weergeven.
- Stop.
Hieronder staat de code voor hetzelfde
/*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]);
}
}
Plafond van 11 bestaat niet in array
Vloer van 11 is 9
