Floor and Ceil in Sorted Array in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the floor value in a sorted array.

DSA Python

def find_floor(arr, x):
    low, high = 0, len(arr) - 1
    floor_val = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] [1] x:
            floor_val = arr[mid]
            low = mid + 1
        else:
            high = mid - 1
    return floor_val

Drag options to blanks, or click blank then click option'

A>

B>=

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<=' causes missing correct floor values.

Not updating low and high pointers correctly.

We check if arr[mid] is less than or equal to x to update the floor value.

2fill in blank

medium

Complete the code to find the ceil value in a sorted array.

DSA Python

def find_ceil(arr, x):
    low, high = 0, len(arr) - 1
    ceil_val = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] [1] x:
            ceil_val = arr[mid]
            high = mid - 1
        else:
            low = mid + 1
    return ceil_val

Drag options to blanks, or click blank then click option'

A<=

B>=

C<

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>=' causes missing correct ceil values.

Not updating low and high pointers correctly.

We check if arr[mid] is greater than or equal to x to update the ceil value.

3fill in blank

hard

Fix the error in the binary search condition to correctly find the floor.

DSA Python

def find_floor(arr, x):
    low, high = 0, len(arr) - 1
    floor_val = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] [1] x:
            floor_val = arr[mid]
            low = mid + 1
        else:
            high = mid - 1
    return floor_val

Drag options to blanks, or click blank then click option'

A<=

B>=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<=' causes wrong floor results.

Confusing floor with ceil logic.

The condition must be 'arr[mid] <= x' to find the floor correctly.

4fill in blank

hard

Fill both blanks to complete the binary search for ceil value.

DSA Python

def find_ceil(arr, x):
    low, high = 0, len(arr) - 1
    ceil_val = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] [1] x:
            ceil_val = arr[mid]
            high = mid [2] 1
        else:
            low = mid + 1
    return ceil_val

Drag options to blanks, or click blank then click option'

A>=

B<=

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<=' instead of '>=' causes wrong ceil results.

Adding 1 to high instead of subtracting.

Use '>=' to check if arr[mid] is greater or equal to x, and subtract 1 from high to search left.

5fill in blank

hard

Fill all three blanks to create a dictionary of floors for each element in a list.

DSA Python

def find_floor(arr, x):
    low, high = 0, len(arr) - 1
    floor_val = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] [1] x:
            floor_val = arr[mid]
            low = mid + 1
        else:
            high = mid - 1
    return floor_val

nums = [1, 3, 5, 7, 9]
queries = [4, 8, 10]
floor_map = { [2]: find_floor(nums, [3]) for [2] in queries }

Drag options to blanks, or click blank then click option'

A<=

Bq

Cqueries

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operator in condition.

Using incorrect variable names in dictionary comprehension.

Use '<=' in the condition, and 'q' as the loop variable for queries.

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