Find Floor in a Sorted Array in Python
In a sorted array floor of value (say, x) means the maximum value present in the array which is less than or equal to that value (x). Let’s clarify the problem with some examples:
Array : 2, 4, 7, 9, 11, 12 Floor(7) : 7 Array : 2, 4, 7, 9, 11, 12 Floor(6) : 4 Array : 2, 4, 7, 9, 11, 12 Floor(1) : -1 # As floor of 1 doesn't exist Array : 2, 4, 7, 9, 11, 12 Floor(15) : 12
In this tutorial, we are going to learn how to find the floor in a sorted array in Python language.
Approach:
Here, we are going to use the concept of binary search in order to solve our problem. First, we go to the middle. If the desired value is somewhere at left or right then we will check for the left or right part accordingly. For the subpart, we will check in a similar way. To know more about binary search, click here.
Suppose we have an array of N elements. To check for the floor of any number in this array we have to compare logN times. For a number that is equal to the largest element or greater than all the elements of the array, the floor value is the last element of the array. And for a number that is smaller than all the elements of the array, the floor value is -1 (as floor value doesn’t exist in this case). So, before starting logN comparisons we will first check for the last element and for the first element, such that logN comparisons can be avoided in some test cases. Let’s jump into code.
Code:
Below is our Python code that will be going to help to find the floor in a sorted array:
# function to compute floor value def floor_value(arr, x): # length of array l = len(arr) # Checking for last element if(x >= arr[l-1]): return arr[l-1] # Checking for first element if(x < arr[0]): return -1; # setting up the initial parameters beg = 0 end = l-1 rel = -1 # comparing logN times to get floor value while(beg <= end): mid = int(beg + (end-beg)/2) # eliminating the right subarray if(x < arr[mid]): end = mid-1 # eliminating the left subarray else: rel = arr[mid] beg = mid+1 # returning the floor value return rel def main(): # our test array arr = [2, 4, 7, 9, 11, 12] # different queries to test queries = [7, 6, 1, 15] # testing for i in queries: print(floor_value(arr, i)) if __name__ == '__main__': main()
Output:
7 4 -1 12
Complexity Analysis:
This is simply a binary search. So, the time complexity will be O(logN) and space complexity will be O(1), where N is the size of the array.
Leave a Reply