Floor and Ceil in Sorted Array in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find floor and ceil of 7 in a sorted array

What is the output of the following code that finds floor and ceil of 7 in the array?

DSA Python

def floor_ceil(arr, x):
    floor = -1
    ceil = -1
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid], arr[mid]
        elif arr[mid] < x:
            floor = arr[mid]
            start = mid + 1
        else:
            ceil = arr[mid]
            end = mid - 1
    return floor, ceil

arr = [1, 3, 5, 6, 8, 9]
x = 7
print(floor_ceil(arr, x))

A (-1, -1)

B (5, 6)

C (7, 7)

D (6, 8)

💡 Hint

Think about how binary search narrows down the floor and ceil values.

The floor of 7 is the greatest element less than or equal to 7, which is 6. The ceil is the smallest element greater than or equal to 7, which is 8.

❓ Predict Output

intermediate

Output when element is smaller than all array elements

What is the output of the code when searching floor and ceil of 0 in the array?

DSA Python

def floor_ceil(arr, x):
    floor = -1
    ceil = -1
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid], arr[mid]
        elif arr[mid] < x:
            floor = arr[mid]
            start = mid + 1
        else:
            ceil = arr[mid]
            end = mid - 1
    return floor, ceil

arr = [2, 4, 6, 8, 10]
x = 0
print(floor_ceil(arr, x))

A (0, 2)

B (-1, 2)

C (-1, -1)

D (2, 4)

💡 Hint

If x is smaller than all elements, floor should be -1.

Since 0 is smaller than all elements, floor remains -1 (no smaller element), ceil is the smallest element 2.

🔧 Debug

advanced

Identify the error in floor and ceil function

What error does the following code produce when run?

DSA Python

def floor_ceil(arr, x):
    floor = None
    ceil = None
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            return arr[mid], arr[mid]
        elif arr[mid] < x:
            floor = arr[mid]
            start = mid + 1
        else:
            ceil = arr[mid]
            end = mid - 1
    return floor, ceil

arr = []
x = 5
print(floor_ceil(arr, x))

A TypeError: 'NoneType' object is not subscriptable

B IndexError: list index out of range

C (None, None)

D ValueError: empty array

💡 Hint

Consider what happens when the array is empty and the function returns floor and ceil.

The function returns (None, None) because floor and ceil are initialized as None and no updates happen.

🧠 Conceptual

advanced

Floor and Ceil when element is present in array

If the element x is present in the sorted array, what will be the floor and ceil values returned by the function?

A Both floor and ceil will be x

B Floor will be x, ceil will be next element

C Floor will be previous element, ceil will be x

D Floor and ceil will be the closest smaller and larger elements respectively

💡 Hint

Check the condition when arr[mid] == x in the code.

When x is found, the function returns (x, x) immediately as floor and ceil.

🚀 Application

expert

Number of elements between floor and ceil

Given a sorted array and a number x, how many elements lie strictly between the floor and ceil of x?

DSA Python

def count_between_floor_ceil(arr, x):
    floor = -1
    ceil = -1
    start, end = 0, len(arr) - 1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == x:
            floor = ceil = arr[mid]
            break
        elif arr[mid] < x:
            floor = arr[mid]
            start = mid + 1
        else:
            ceil = arr[mid]
            end = mid - 1
    if floor == -1 or ceil == -1 or floor == ceil:
        return 0
    floor_index = arr.index(floor)
    ceil_index = arr.index(ceil)
    return max(0, ceil_index - floor_index - 1)

arr = [1, 3, 5, 7, 9, 11]
x = 6
print(count_between_floor_ceil(arr, x))

A 0

B 1

C 2

D 3

💡 Hint

Find the indices of floor and ceil and count elements between them.

Floor is 5 at index 2, ceil is 7 at index 3, so elements strictly between are zero because indices are adjacent.

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