Welcome to this comprehensive lesson on Data Structures and Algorithms! Today, we'll dive into finding Floor and Ceil, two essential concepts every programmer should know. Let's get started!
In the context of data structures, finding the Floor and Ceil of a number is a way to find the closest smaller (Floor) and larger (Ceil) numbers in a given sorted array.
š” Pro Tip: These concepts are particularly useful when working with sorted data structures, such as sorted arrays and sorted linked lists.
The Floor of a number x in a sorted array is the largest number in the array that is less than or equal to x.
Let's consider an example:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 7
# In this case, the Floor of 7 in the array is 7 itself.The Ceil of a number x in a sorted array is the smallest number in the array that is greater than or equal to x.
Let's consider the same example as above:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 7
# In this case, the Ceil of 7 in the array is 7. But if we want to find the smallest number that is greater than 7, it is 8.Now that we understand what Floor and Ceil are, let's see how we can find them in Python.
def find_floor(arr, x):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == x:
return arr[mid] # If the number is present, return itself as both the floor and the number itself
if arr[mid] > x:
end = mid - 1
else:
start = mid + 1
return arr[start] # Return the number at the start if it is smaller than xdef find_ceil(arr, x):
start = 0
end = len(arr) - 1
while start <= end:
mid = (start + end) // 2
if arr[mid] == x:
return arr[mid + 1] # If the number is present, return the next number as it's the smallest number greater than x
if arr[mid] > x:
end = mid - 1
else:
start = mid + 1
return arr[-1] # If x is greater than all numbers in the array, return the last numberNow that we have our functions for finding Floor and Ceil, let's see them in action:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 7
print("Floor of", x, "is", find_floor(arr, x))
print("Ceil of", x, "is", find_ceil(arr, x))What is the Floor of the number 10 in the given sorted array `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`?
What is the Ceil of the number 2 in the given sorted array `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`?