Find Floor in a Sorted Array in Python

By Shoif Md Mia

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.