Floor and Ceil in Sorted Array in DSA Python

Mental Model

Find the closest smaller or equal value (floor) and closest greater or equal value (ceil) to a target in a sorted list.

Analogy: Imagine standing on a number line with sorted stepping stones. Floor is the stone you stand on or just behind you, ceil is the stone you stand on or just ahead.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: closest ≤ 6
Ceil: closest ≥ 6

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target: 6

Goal: Find floor and ceil values for 6 in the array

Step 1: Start binary search with low=0, high=4

[1] -> [3] -> [5] -> [7] -> [9] -> null, target=6, low=0, high=4

Why: We begin searching the whole array to find floor and ceil

Step 2: Calculate mid=2, value=5; 5 < 6, update floor=5, move low to mid+1=3

[1] -> [3] -> [5↑] -> [7] -> [9] -> null, floor=5, low=3, high=4

Why: 5 is less than target, so it can be floor; search right half for closer values

Step 3: Calculate mid=3, value=7; 7 > 6, update ceil=7, move high to mid-1=2

[1] -> [3] -> [5] -> [7↑] -> [9] -> null, floor=5, ceil=7, low=3, high=2

Why: 7 is greater than target, so it can be ceil; search left half for closer values

Step 4: Since low > high, stop search; floor=5, ceil=7 found

[1] -> [3] -> [5] -> [7] -> [9] -> null, floor=5, ceil=7

Why: Search ended, floor and ceil are closest values around target

Result:

Floor: 5
Ceil: 7

Annotated Code

DSA Python

class SortedArrayFloorCeil:
    def __init__(self, arr):
        self.arr = arr

    def find_floor_ceil(self, target):
        low, high = 0, len(self.arr) - 1
        floor, ceil = None, None
        while low <= high:
            mid = (low + high) // 2
            if self.arr[mid] == target:
                return self.arr[mid], self.arr[mid]  # exact match is both floor and ceil
            elif self.arr[mid] < target:
                floor = self.arr[mid]  # update floor
                low = mid + 1  # search right half
            else:
                ceil = self.arr[mid]  # update ceil
                high = mid - 1  # search left half
        return floor, ceil


if __name__ == '__main__':
    arr = [1, 3, 5, 7, 9]
    target = 6
    finder = SortedArrayFloorCeil(arr)
    floor, ceil = finder.find_floor_ceil(target)
    print(f"Floor: {floor}")
    print(f"Ceil: {ceil}")

while low <= high:

continue searching while search space is valid

mid = (low + high) // 2

find middle index to check value

if self.arr[mid] == target:

if exact match, floor and ceil are the same

elif self.arr[mid] < target:

update floor and move search to right half

else:

update ceil and move search to left half

Output

Floor: 5

Ceil: 7

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive linear search takes O(n) by scanning all elements; binary search is faster for sorted arrays

Edge Cases

target smaller than all elements

floor is None, ceil is first element

DSA Python

return floor, ceil

target larger than all elements

floor is last element, ceil is None

DSA Python

return floor, ceil

target exactly matches an element

floor and ceil both equal target

DSA Python

if self.arr[mid] == target:

When to Use This Pattern

When asked to find closest smaller or larger values in a sorted list, use binary search to efficiently find floor and ceil.

Common Mistakes

Mistake: Not updating floor or ceil correctly when moving search boundaries
Fix: Update floor when moving right and ceil when moving left inside the binary search loop

Summary

Find the closest smaller or equal (floor) and closest greater or equal (ceil) values to a target in a sorted array.

Use when you need quick lookups of nearest values around a target in sorted data.

The key insight is to use binary search to narrow down floor and ceil candidates efficiently.

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