Find loft- og gulvværdien af et element i et givet sorteret array
I denne vejledning lærer vi, hvordan man finder loft- og gulvværdien af et element i et givet sorteret array. Men før du går videre, hvis du ikke er bekendt med begreberne for arrayet, så tjek artiklen Arrays in Java.
Input:
Array:15 17 18 19 20 21 22 24 25 26 27
Element:16
Output:
Etage:15
Loft:17
Ovenstående problem kan løses på to måder:
Metode 1:Binær søgning
Metode 2:Lineær søgning
Lad os se på hver af disse metoder separat.
Program 1:Sådan finder du loft- og gulvværdien af et element i et givet sorteret array
I denne tilgang udfører vi simpelthen en binær søgning for at finde gulv- og loftværdien af et element i et givet sorteret array.
Algorithme
- Start
- Deklarer en matrixstørrelse.
- Bed brugeren om at initialisere matrixstørrelsen.
- Deklarer en matrix.
- Bed brugeren om at initialisere arrayet.
- Deklarer en variabel for at gemme værdien af det element, der skal søges i.
- Kald en metode for at tjekke for loftværdien.
- Initialiser loftet til -1, og gentag derefter elementerne for at søge efter loftværdien.
- I ceil-metoden, hvis x er lig med det midterste element, så er det ceil-værdien.
- Hvis x er mindre end det midterste element, så ligger loftværdien i venstre underarray. Opdater loftværdien og søg igen efter den i A[low,mid-1].
- Hvis x er større end det midterste element, så ligger loftværdien i det højre underarray. Opdater loftværdien, og søg igen efter den i A[mid,end]. Returner den fundne loftværdi.
- Ring til en metode for at kontrollere bundværdien.
- Initialiser gulvet til -1, og gentag derefter elementerne for at søge efter etageværdien.
- I etagemetoden, hvis x er lig med det midterste element, så er det etageværdien.
- Hvis x er mindre end det midterste element, så ligger etageværdien i venstre underarray. Opdater bundværdien og søg igen efter den i A[low,mid-1].
- Hvis x er større end det midterste element, så ligger etageværdien i højre underarray. Opdater bundværdien og søg igen efter den i A[midt,high].
- Returner den fundne bundværdi.
- Vis både loft- og gulvværdi.
- Stop
Nedenfor er koden til det samme.
Nedenstående program demonstrerer, hvordan man finder loft- og gulvværdien af et element i et givet sorteret array
// 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;
}
}
Indtast størrelsen af arrayet:10
Indtast array-elementerne:1 2 3 4 6 7 8 9 10 11
Indtast det element, hvis gulv- og loftværdier du vil kontrollere:5
Loftværdi er 6
gulvværdi er 4
Program 2:Sådan finder du loft- og gulvværdien af et element i et givet sorteret array
I denne tilgang udfører vi simpelthen en lineær søgning for at finde gulv- og loftværdien af et element i et givet sorteret array.
Algorithme
- Start
- Deklarer et sorteret array.
- Deklarer en variabel for at gemme længden af det sorterede array.
- Indtast det tal, hvis gulv- og loftværdi du vil kontrollere.
- For at finde etageværdien skal du gå gennem arrayet.
- Hvis det aktuelle element er større end det indtastede element, skal du udskrive det forrige tal og bryde løkken.
- Hvis der ikke er et tal, der er større end det indtastede element, så udskriv det sidste element
- Hvis det første tal er større end det indtastede element, så udskriv -1.
- Tilsvarende, hvis det indtastede element er mindre end eller lig med det første element i arrayet, returneres 0.
- Ellers gå gennem arrayet for at finde et tal, der er mindre end det indtastede tal.
- Hvis der ikke findes et sådant element, så returner -1.
- Vis begge resultater.
- Stop.
Nedenfor er koden til det samme
/*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]);
}
}
Loft på 11 findes ikke i array
Etage på 11 er 9
