Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Find the Floor and Ceil of a Number

Explore how to apply a modified binary search algorithm to determine the floor and ceil of a target number in a sorted array. This lesson guides you through step-by-step code explanations that illustrate how to update search boundaries and maintain efficient searching to achieve a time complexity of O(log n).

We'll cover the following...

Solution

We can make use of the fact that the array is sorted. So, by a little modification of the binary search algorithm, we can successfully crack this problem. The core idea remains the same: we divide the array at the midpoint and search for the key either in left or right subarray based on the comparison with a given number.

Here is the complete working solution:

Java
class FloorCeiling {
 
 public static int findFloor(int[] arr, int x) // Function to find floor of x in a sorted array arr[]
 {
  int left = 0, right = arr.length - 1;
  int floor = -1; // initialize floor to -1, if -1 is returned as it is, then floor does not exist!
  while (left <= right) {
   
   int mid = (left + right) / 2; // find the middle value
   if (arr[mid] == x) // if x is equal to mid element, it is the floor value
    return arr[mid];
   else if (x < arr[mid]) // if x is less than the mid element, floor exists in the left subArr[left...mid-1]
    right = mid - 1;
   else // if x is more than the mid element, floor exists in the right subArr[mid...right].  
   {
    floor = arr[mid];
    left = mid + 1;
   }
  }
  return floor;
 }
 public static int findCeiling(int[] arr, int x) // Function to find ceiling of input x in a sorted array
 {
  int left = 0, right = arr.length - 1;
  int ceil = -1; // initialize ceiling value to -1, if -1 is returned as it is, then ceil doesnot exit!
  while (left <= right) {
   
   int mid = (left + right) / 2; // find the middle value 
   if (arr[mid] == x) // if x is equal to middle element, it is the ceiling 
    return arr[mid];
   else if (x < arr[mid]) // if x is less than the mid element, ceil exists in the left subArray[left...mid-1]
   {
    ceil = arr[mid];
    right = mid - 1;
   } else // if x is more than the mid element, ceil exists in the right subArr[mid...right]
    
    left = mid + 1;
  }
  return ceil;
 }
 // wraper function to call both Floor and Ceiling Functions and then store the output in the `output` array
 public static void findFloorCeiling(int[] input, int x, int[] output) {
  
  output[0] = findFloor(input, x);
  output[1] = findCeiling(input, x);
 }
}
class Driver {
 public static void main(String[] args) {
  int[] inputs = {1, 2, 3, 5, 7};
  int[] output = new int[2];
  FloorCeiling.findFloorCeiling(inputs, 4, output);
  System.out.println("Floor and Ceil of 4 is: " + Arrays.toString(output));
 }
}

Explanation

Let’s take you to the step-by-step code break down to gain a better understanding of the solution:

  • Line 44 - 48: The wrapper function explicitly calls findFloor(input, x) and findCeiling(input, x), respectively, and stores the result in the array called output.

floorfloor ...