Floor (Lower Bound)

Question

Find the Floor - The largest Element before the Target Element(if the element exists in the array simply return that as the floor)

array = [1, 2, 8, 10, 10, 12, 19] element = 5

Floor = 2

Math

Ceil is the upper limit of a decimal number. In this problem, since we are dealing with integers, we will consider the element after the target element, or the target element itself if it is present in the array as the upper limit or ceil.

Intuition

1. We are looking for the largest element before the target element, also if the target element exists that is simply our floor.
2. A simple way to find the floor is to perform a linear search, where we scan all the elements starting from index 0 and return the last element before we encounter anything greater than the target. If a larger element is, the loop breaks and the function returns the current floor. This solution has a time complexity of O(n), where n is the length of the array.
Copy

def find_floor(arr, target):
    floor = -1
    for i in range(len(arr)):
        if arr[i] > target:
            break
				else:
	        floor = arr[i]
    return floor

3. But since the array is sorted, is there a way we can do this in logarithmic time? We will need to make a binary decision. What is that binary decision that will help us more closer to the target ?
4. Think of halves: When we are in the upper half all values will be greater than the target, the target will be to the left, so we discard all elements to the right. Conversely, when in the lower half all values will be less than the target, the target will be to the right, so we discard all elements to the left.
5. If the target exists in the array we can include it in the lower half, since we have to return it as an edge value.
6. We hop between each half, chopping elements and reducing the range. When we cut the last element from the lower half, it will either be the target or the largest value smaller than the target. We keep track of the most up-to-date floor and return it.


a. If the target value is present in the array, the upper bound or ceiling will be equal to the target value. As an example, in the array [1, 2, 5, 10, 10, 12, 19], if the target value is 5, the floor or lower bound will be 5.

Implementation

1. This is similar to the problem of 🔑Find the First True in a Sorted Boolean Array . However, in this case, the true values are on the left side instead of the right so the problem is reduced to finding the last true element in a boolean array— the last element in the lower half.
2. When in the lower half (true), the target will be to the right, so we discard all elements to the left. Conversely, when in the upper half (false values), the target will be to the left, so we discard all elements to the right.
Copy

#True
if target >= nums[mid]:
    possibleValue = mid
    left = mid + 1

Copy

#False
else: # target < nums[mid]:
	right = mid - 1

3. Keep chopping elements' and reducing the range until the range is exhausted(left and right pointers overlap)
1. The last element chopped from the lower half will be our floor, which will be tracked and returned.

Floor Code

SandBox PythonTutor (Visualized)

Take Aways

🎢Floor (Lower Bound) and 🛖Ceiling(Upper Bound) ) are frameworks to reframe complex problems into simpler challenges. In the Binary Search roadmap, I solved the same problem with both of these techniques: 🎏Search Insert Position(Sorted Array) Upper Bound and Search Insert Position(Sorted Array) lower Bound. How you use them is up to you; reframing some problems works better with one or the other.

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition