Floor and Ceil in Sorted Array in DSA Python - Build from Scratch

Floor and Ceil in Sorted Array

📖 Scenario: You are working on a simple search tool that helps users find the closest numbers in a sorted list. When a user enters a number, the tool will find the floor (the greatest number less than or equal to the input) and the ceil (the smallest number greater than or equal to the input) from the list.

🎯 Goal: Build a program that finds the floor and ceil of a given number in a sorted array.

📋 What You'll Learn

Create a sorted list of integers

Create a variable for the target number to search floor and ceil for

Write logic to find floor and ceil values from the list

Print the floor and ceil values

💡 Why This Matters

🌍 Real World

Finding floor and ceil values is useful in many real-world applications like price filtering, range queries, and recommendation systems.

💼 Career

Understanding how to find closest values in sorted data is a common task in software development, data analysis, and algorithm design.

1

Create the sorted list

Create a list called numbers with these exact integers in ascending order: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

DSA Python

# Create the sorted list called numbers
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set the target number

Create a variable called target and set it to the integer 20

DSA Python

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# Create the target number variable
# Your code here

Hint

Use a simple assignment to create the variable target.

3

Find floor and ceil values

Write code to find the floor and ceil of target in numbers. Use variables floor and ceil. Initialize floor to None and ceil to None. Use a for loop with variable num to check each number in numbers. If num is less than or equal to target, update floor. If num is greater than or equal to target and ceil is None, update ceil and break the loop.

DSA Python

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 20
# Find floor and ceil values
# Your code here

Hint

Loop through the list and update floor when number is less or equal to target. Update ceil once when number is greater or equal to target and then stop.

4

Print the floor and ceil

Print the floor and ceil values using print statements exactly as: Floor: <floor> and Ceil: <ceil> where <floor> and <ceil> are the variable values.

DSA Python

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 20
floor = None
ceil = None
for num in numbers:
    if num = target and ceil is None:
        ceil = num
        break
# Print floor and ceil values
# Your code here

Hint

Use two print statements to show floor and ceil with labels.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The greatest element less than or equal to the number

B. The smallest element greater than the number

C. The average of all elements less than the number

D. The smallest element less than the number

Solution

1. Step 1: Understand floor definition in sorted array

   The floor of a number is the greatest element in the array that is less than or equal to the given number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly, others describe different concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option A

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Choosing smallest element greater than number
• Thinking floor is average of smaller elements

2. Which of the following is the correct Python syntax to find the floor of x in a sorted list arr using binary search?

easy

A. Use bisect_left and check index-1 element

B. Use bisect_right and check index-1 element

C. Use bisect_left and check index element

D. Use bisect_right and check index element

Solution

1. Step 1: Recall bisect_right usage for floor

   bisect_right(arr, x) returns insertion point to the right of existing entries equal to x.

2. Step 2: Find floor index using bisect_right

   The floor is at index bisect_right(arr, x) - 1 if index is valid.

3. Final Answer:

   Use bisect_right and check index-1 element -> Option B

4. Quick Check:

   Floor index = bisect_right - 1 [OK]

Hint: Floor index = bisect_right(arr, x) - 1 [OK]

Common Mistakes:

• Using bisect_left for floor without adjusting index
• Checking index instead of index-1
• Confusing bisect_left and bisect_right roles

3. Given a sorted array arr = [1, 2, 4, 6, 8, 10], write a function to find the floor and ceil of x = 5. What should the function return?

easy

A. [5, 6]

B. [2, 6]

C. [4, 5]

D. [4, 6]

Solution

1. Step 1: Identify floor of 5 in arr

   Floor is greatest element ≤ 5, which is 4.

2. Step 2: Identify ceil of 5 in arr

   Ceil is smallest element ≥ 5, which is 6.

3. Final Answer:

   [4, 6] -> Option D

4. Quick Check:

   Floor = 4, Ceil = 6 [OK]

Hint: Floor ≤ x, Ceil ≥ x; pick closest elements [OK]

Common Mistakes:

• Returning x if not in array
• Confusing floor and ceil values
• Choosing elements not closest to x

4. What is the output of the following code?

import bisect
arr = [1, 3, 5, 7, 9]
x = 6
floor_index = bisect.bisect_right(arr, x) - 1
ceil_index = bisect.bisect_left(arr, x)
print(arr[floor_index], arr[ceil_index])

medium

A. 5 7

B. 5 5

C. 3 7

D. 7 9

Solution

1. Step 1: Calculate floor_index using bisect_right

   bisect_right(arr, 6) returns 3 (position after 5), so floor_index = 3 - 1 = 2, arr[2] = 5.

2. Step 2: Calculate ceil_index using bisect_left

   bisect_left(arr, 6) returns 3 (position of 7), so ceil_index = 3, arr[3] = 7.

3. Final Answer:

   5 7 -> Option A

4. Quick Check:

   Floor = 5, Ceil = 7 [OK]

Hint: Floor uses bisect_right-1, Ceil uses bisect_left [OK]

Common Mistakes:

• Using bisect_left for floor index
• Mixing floor and ceil indices
• Off-by-one errors in indexing

5. The following code tries to find the floor of x in a sorted list arr. What is the error?

import bisect
arr = [2, 4, 6, 8]
x = 1
index = bisect.bisect_right(arr, x) - 1
print(arr[index])

medium

A. IndexError when x is smaller than all elements

B. SyntaxError due to bisect usage

C. Wrong floor value printed

D. No error, code works fine

Solution

1. Step 1: Calculate index for x=1

   bisect_right(arr, 1) returns 0, so index = 0 - 1 = -1.

2. Step 2: Issue with negative index

   arr[-1] accesses the last element 8 due to Python's negative indexing, but since 1 < arr[0], no element ≤1 exists, so 8 is the wrong floor value.

3. Final Answer:

   Wrong floor value printed -> Option C

4. Quick Check:

   index < 0 means no floor [OK]

Hint: Check if index < 0 before accessing floor [OK]

Common Mistakes:

• Not handling case when x < smallest element
• Assuming floor always exists
• Ignoring negative indices in Python lists