Find the ceil and floor value of an element in a given sorted array

In this tutorial, we will learn how to find the ceiling and floor value of an element in a given sorted array. But before moving forward, if you are not familiar with the concepts of the array, then do check the article Arrays in Java.

Input:

Array:15 17 18 19 20 21 22 24 25 26 27

Element: 16

Output:

Floor: 15

Ceil: 17

The above problem can be solved in two ways:

Method 1: Binary Search

Method 2: Linear Search

Let us look at each of these methods separately.

Program 1: To Find the Ceil and Floor value of an Element in a given Sorted Array

In this approach, we simply perform a binary search to find the floor and ceil value of an element in a given sorted array.

Algorithm

1. Start
2. Declare an array size.
3. Ask the user to initialize the array size.
4. Declare an array.
5. Ask the user to initialize the array.
6. Declare a variable to store the value of the element to be searched.
7. Call a method to check for the ceil value.
8. Initialize the ceil to -1 and then iterate through the elements to search for the ceil value.
9. In the ceil method, If x is equal to the middle element, then it is the ceil value.
10. If x is less than the middle element, then the ceil value lies in the left sub array. Update the ceil value and again search for it in the A[low,mid-1].
11. If x is greater than the middle element, then the ceil value lies in the right sub array. Update the ceil value and againn search for it in the A[mid,end].Return the ceil value found.
12. Call a method to check for the floor value.
13. Initialize the floor to -1 and then iterate through the elements to search for the floor value.
14. In the floor method, If x is equal to the middle element, then it is the floor value.
15. If x is less than the middle element, then the floor value lies in the left subarray. Update the floor value and again search for it in the A[low,mid-1].
16. If x is greater than the middle element, then the floor value lies in the right subarray. Update the floor value and again search for it in the A[mid,high].
17. Return the floor value found.
18. Display both the ceiling and floor value.
19. Stop

Below is the code for the same.

The below program demonstrates on how to find the ceil and floor value of an element in a given sorted 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;
    }
}

Enter the size of the array: 10
Enter the array elements: 1 2 3 4 6 7 8 9 10 11
Enter the element whose floor and ceil values you want to check: 5
Ceil value is 6
floor value is 4

Program 2: To Find the Ceil and Floor value of an Element in a given Sorted Array

In this approach, we simply perform a linear search to find the floor and ceiling value of an element in a given sorted array.

Algorithm

1. Start
2. Declare a sorted array.
3. Declare a variable to store the length of the sorted array.
4. Enter the number whose floor and ceiling value you want to check.
5. To find the floor value traverse through the array.
6. If the current element is greater than the element entered then print the previous number and break the loop.
7. If there is no number greater than the element entered then print the last element
8. If the first number is greater than the element entered then print -1.
9. Similarly, if the element entered is smaller than or equal to the first element in the array then return 0.
10. Else traverse through the array to find a number smaller than the entered number.
11. If no such element is found, then return -1.
12. Display both the results.
13. Stop.

Below is the code for the same

/*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]); 
    }   
} 

Ceiling of 11 doesn't exist in array
Floor of 11 is 9