In this article, we are going to see various methods of finding the floor of a given number from a given sorted array. To solve this efficiently, the concept of Divide and Conquer / Binary Search is required.

Table of contents:

1. What does floor of a number mean?
2. Linear search solution for floor of a number
3. Implementation of Linear Search solution for floor of a number
4. Complexity of linear search solution method
5. Binary Search solution
6. Implementation of binary search solution
7. Complexity of binary search solution method

Pre-requisites:

• Binary Search Algorithm
• Applications of Binary Search
• Iterative and Recursive Binary Search Algorithm
• Time & Space Complexity of Binary Search

Firstly, we need to look at what floor of a number actually means.

What does floor of a number mean?

The floor of a number is greatest integer less than or equal to that number.
Suppose, we need to find floor of a number x, then we would mathematically denote it as "⌊x⌋".

For e.g. :-

If we have to find the floor of 4.3, the according to the definition of floor, the floor of 4.3 will be the largest integer which is less than or equal to 4.3 ,thus it will be 4 as it is the largest integer which is less than or equal to that number.

Another example:-

If we have to find the floor of 4, then its floor will also be equal to 4, as 4 itself is the largest integer less than or equal to that number.
So, from the above examples we can see that floor of an integer is always equal to that integer, and that of a decimal is that number minus the fractional part of that decimal number.

Now, since we know the concept of floor function we can now focus on the various methods of finding the floor of a given number from a given sorted array.

Linear search solution for floor of a number

This solution resembles the basic linear search in its approach.
In this method, we simply traverse the array till we find an integer which is greater than the number of which we have to find floor of. Then, the previous indexed value in the array will be our floor of the given number in the given sorted array.

Steps of the algorithm:-

1. Check each value in the array with the given number.
2. If the value is lesser than the given number then, continue to iterate till we find the number which is greater than or equal to the given number.
3. If the value in the array at that index is equal to the given number then, that value will be our floor .
4. If the value in the array at that index is greater than the given number, then, the floor of the given number would be the value at the index just previous to the current element.

Implementation of Linear Search solution for floor of a number

#include <iostream>
using namespace std;

int Floor_of_number(int sorted_arr[], int n, int number){
/*If the number of which we need to find the floor is lesser than the first element then according to the definition of floor function its value can't be found.*/
   if (number < sorted_arr[0])
   {   
      cout<<"Floor of this value can't be found";
      return -1;
   }
/*If number of which we need to find the floor is greater than the greatest element in the array then that greatest element will be the floor of that number.*/ 
   if (number >= sorted_arr[n - 1])
      return sorted_arr[n-1];
//Traversing the loop to find floor
   for (int i = 0; i < n; i++)
      if (sorted_arr[i] > number)
         return sorted_arr[i - 1];
}
int main(){
   int n;
   cout<<"Enter the size of the array";
   cin>>n;
   int sorted_arr[n];
   for(int i=0;i<n;i++)
   {
   cout<<"Enter the"<<i+1<<"th value in the array";
   cin>>sorted_arr[i];
   }
   int number;
   cout<<"Enter the number of which we have to fin the floor of";
   cin>>number;
   int floor = Floor_of_number(sorted_arr, n,number);
   if (floor== -1)
      cout<<"The floor of "<<number<<" doesn't exist in the array";
   else
      cout<<"The floor of "<<number<<" in the array is "<<floor;
   return 0;
}

Complexity of linear search solution method

Time complexity of this code is O(n) , while space complexity is O(1) .

Binary Search solution

In this, we use a solution which resembles the binary search method of finding the floor of a given number in the sorted array.
Basically, in this method we reduce the size of the array by half till we either get the number which is equal to the number for which we have to find the floor, or till we reach the stage at which low and high are same, then that number would be the solution, of our problem.

Steps of the algorithm:-

1. Declare two variables low and high with low=index of the first element in the array and high=index of the last element in the array.
2. Declare a mid variable with mid=(low+high)/2.
3. Compare the mid variable with the number of which we have to find th floor.
4. If mid variable equals the number then, return that mid variable's value as that will be our solution.
5. Else if number value is less than the mid value then make high=mid-1, and again do the steps from 2-4.
6. Or if number value is greater than the mid value then make low=mid+1, and do the steps from 2-4.
7. If low=high, then mid will also be equal to low which in turn be equal to high, and if number is not equal to that of mid value then the value just previously indexed of mid will be our solution.

Implementation of binary search solution

#include <iostream>
using namespace std;

int Floor_of_Number(int sorted_arr[], int low, int high, int number){
/*If number is more than the last element then, floor will be value at last index.*/
   if (number >= sorted_arr[high])
      return sorted_arr[high];
   int mid = (low + high) / 2;
 //If mid is equal to the number then, that value will be our floor.
   if (sorted_arr[mid] == number)
      return sorted_arr[mid];
 /*If number is less than the value at mid index, then, update the high to mid-1 and recur the function one more time.*/ 
   if (number < sorted_arr[mid])
      return Floor_of_Number(sorted_arr, low, mid - 1, number);
/* If number is more than the value at mid index, then, update the low to mid+1 and recur the function one more time.*/   
   if(number>sorted_arr[mid])
      return Floor_of_Number(sorted_arr, mid + 1, high, number);
}
int main(){
   int arr[] = {1,2,3,4,5,7,8,11};
   int n = sizeof(arr) / sizeof(arr[0]);
   int  number = 9;
   int floor = Floor_of_Number(arr, 0, n - 1, number );
   if (floor == -1)
      cout<<"The floor of "<<number<<" doesn't exist in the array";
   else
      cout<<"The floor of "<<number<<" in the array is "<<floor;
   return 0;
}

Complexity of binary search solution method

Time complexity of this solution is O(log(n)) , where 'n' is the size of the array.
Space complexity of this solution is O(1) , as the spaces allocated does not depend upon the input.

With this article at OpenGenus, you must have the complete idea of how to find floor of a number in a sorted array.