Floor and Ceil in Sorted Array in DSA Rust

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 can step on that is just before or exactly where you stand. Ceil is the stone you can step on that is just after or exactly where you stand.

Sorted Array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: ?
Ceil: ?

Dry Run Walkthrough

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

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

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

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

Why: We use binary search to efficiently find floor and ceil in sorted array

Step 2: Calculate mid=2, mid_value=5; 5 < 6, update floor=5, low=3

[1, 3, 5, 7, 9], floor=5, low=3, high=4

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

Step 3: Calculate mid=3, mid_value=7; 7 > 6, update ceil=7, high=2

[1, 3, 5, 7, 9], floor=5, ceil=7, low=3, high=2

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

Step 4: Since low > high, stop search

floor=5, ceil=7

Why: Search ends when low passes high; floor and ceil found

Result:

Floor: 5
Ceil: 7

Annotated Code

DSA Rust

fn floor_ceil(arr: &[i32], target: i32) -> (Option<i32>, Option<i32>) {
    let mut low = 0;
    let mut high = arr.len().saturating_sub(1);
    if arr.is_empty() {
        return (None, None);
    }
    let mut floor = None;
    let mut ceil = None;

    while low <= high {
        let mid = low + (high - low) / 2;
        let mid_val = arr[mid];

        if mid_val == target {
            return (Some(mid_val), Some(mid_val));
        } else if mid_val < target {
            floor = Some(mid_val); // update floor candidate
            low = mid + 1; // search right half
        } else {
            ceil = Some(mid_val); // update ceil candidate
            if mid == 0 { break; } // prevent underflow
            high = mid - 1; // search left half
        }
    }
    (floor, ceil)
}

fn main() {
    let arr = [1, 3, 5, 7, 9];
    let target = 6;
    let (floor, ceil) = floor_ceil(&arr, target);
    println!("Floor: {}", floor.map_or("None".to_string(), |v| v.to_string()));
    println!("Ceil: {}", ceil.map_or("None".to_string(), |v| v.to_string()));
}

while low <= high {

continue binary search while search space is valid

let mid = low + (high - low) / 2;

calculate middle index to check

if mid_val == target { return (Some(mid_val), Some(mid_val)); }

if exact match found, floor and ceil are target

else if mid_val < target { floor = Some(mid_val); low = mid + 1; }

update floor candidate and search right half

else { ceil = Some(mid_val); if mid == 0 { break; } high = mid - 1; }

update ceil candidate and search left half, prevent underflow

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 would be O(n), checking each element; binary search is much faster for sorted arrays

Edge Cases

empty array

returns (None, None) since no floor or ceil exists

DSA Rust

if arr.is_empty() { return (None, None); }

target smaller than all elements

floor is None, ceil is first element

DSA Rust

else { ceil = Some(mid_val); if mid == 0 { break; } high = mid - 1; }

target greater than all elements

floor is last element, ceil is None

DSA Rust

else if mid_val < target { floor = Some(mid_val); low = mid + 1; }

target exactly matches an element

floor and ceil both equal target

DSA Rust

if mid_val == target { return (Some(mid_val), Some(mid_val)); }

When to Use This Pattern

When you need closest smaller or equal and closest greater or equal values in a sorted list, use binary search to find floor and ceil efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly during binary search
Fix: Update floor when mid_val < target and update ceil when mid_val > target inside the loop

Mistake: Not handling empty array or underflow when mid is 0
Fix: Use saturating_sub for high initialization and break loop if mid is 0 before subtracting

Summary

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

Use when you want to quickly find boundary values around a target in sorted data.

The key is to update floor and ceil candidates during binary search as you narrow down the search space.

Practice

1. What is the floor of a number in a sorted array?

easy

A. The smallest element less than the number

B. The smallest element greater than the number

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

D. The greatest element greater than or equal to 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 ceil or incorrect concepts.

3. Final Answer:

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

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is largest ≤ target in sorted array [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is smallest element
• Ignoring equality in floor definition

2. Which Rust code snippet correctly declares a sorted array of integers?

easy

A. let arr = [1, 3, 5, 7, 9];

B. let arr = (1, 3, 5, 7, 9);

C. let arr = {1, 3, 5, 7, 9};

D. let arr = <1, 3, 5, 7, 9>;

Solution

1. Step 1: Recall Rust array syntax

   Rust arrays use square brackets [] with comma-separated values.

2. Step 2: Check each option

   let arr = [1, 3, 5, 7, 9]; uses correct syntax. let arr = (1, 3, 5, 7, 9); uses tuple syntax with parentheses, let arr = {1, 3, 5, 7, 9}; uses braces resembling sets or blocks, let arr = <1, 3, 5, 7, 9>; uses angle brackets which are invalid.

3. Final Answer:

   let arr = [1, 3, 5, 7, 9]; -> Option A

4. Quick Check:

   Rust arrays use [] [OK]

Hint: Use square brackets [] for arrays in Rust [OK]

Common Mistakes:

• Using parentheses () for arrays
• Using braces {} which are for blocks
• Using angle brackets <> which are invalid here

3. Given the sorted array arr = [2, 4, 6, 8, 10], what is the floor and ceil of 7?

medium

A. Floor = 6, Ceil = 8

B. Floor = 4, Ceil = 6

C. Floor = 8, Ceil = 10

D. Floor = 7, Ceil = 7

Solution

1. Step 1: Find floor of 7 in array

   Floor is greatest element ≤ 7. Elements ≤ 7 are 2,4,6. Greatest is 6.

2. Step 2: Find ceil of 7 in array

   Ceil is smallest element ≥ 7. Elements ≥ 7 are 8,10. Smallest is 8.

3. Final Answer:

   Floor = 6, Ceil = 8 -> Option A

4. Quick Check:

   Floor ≤ 7 = 6, Ceil ≥ 7 = 8 [OK]

Hint: Floor ≤ target, Ceil ≥ target in sorted array [OK]

Common Mistakes:

• Choosing floor or ceil outside array bounds
• Confusing floor and ceil values
• Assuming floor or ceil equals the target always

4. Consider this Rust function to find floor in a sorted array:

fn find_floor(arr: &[i32], target: i32) -> Option<i32> {
    let mut low = 0;
    let mut high = arr.len() - 1;
    let mut floor = None;
    while low <= high {
        let mid = (low + high) / 2;
        if arr[mid] == target {
            return Some(arr[mid]);
        } else if arr[mid] < target {
            floor = Some(arr[mid]);
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    floor
}

What is the bug in this code?

medium

A. Incorrect update of low and high pointers

B. Using arr.len() - 1 without checking if array is empty

C. Returning Some(arr[mid]) instead of index

D. Not handling the case when target is smaller than all elements

Solution

1. Step 1: Analyze initialization of high pointer

   Using arr.len() - 1 causes panic if array is empty because len() is 0 and subtracting 1 underflows.

2. Step 2: Check other parts of code

   Other logic for binary search and floor update is correct. The main bug is unsafe initialization.

3. Final Answer:

   Using arr.len() - 1 without checking if array is empty -> Option B

4. Quick Check:

   Empty array causes panic at arr.len() - 1 [OK]

Hint: Check empty array before subtracting 1 from length [OK]

Common Mistakes:

• Ignoring empty array edge case
• Assuming array always has elements
• Confusing return value with index

5. You have a sorted array arr = [1, 3, 5, 7, 9]. You want to find the floor and ceil for multiple targets: [0, 4, 10]. Which Rust code snippet correctly returns a vector of tuples with floor and ceil for each target? Assume floor or ceil is None if not found.

hard

A. ```rust
fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> {
targets.iter().map(|&t| {
let floor = arr.iter().filter(|&&x| x <= t).min().copied();
let ceil = arr.iter().filter(|&&x| x >= t).max().copied();
(floor, ceil)
}).collect()
}
```

B. ```rust
fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> {
targets.iter().map(|&t| {
let floor = arr.iter().filter(|&&x| x < t).max().copied();
let ceil = arr.iter().filter(|&&x| x > t).min().copied();
(floor, ceil)
}).collect()
}
```

C. ```rust
fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> {
targets.iter().map(|&t| {
let floor = arr.iter().find(|&&x| x <= t).copied();
let ceil = arr.iter().find(|&&x| x >= t).copied();
(floor, ceil)
}).collect()
}
```

D. ```rust
fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> {
targets.iter().map(|&t| {
let floor = arr.iter().filter(|&&x| x <= t).max().copied();
let ceil = arr.iter().filter(|&&x| x >= t).min().copied();
(floor, ceil)
}).collect()
}
```

Solution

1. Step 1: Understand floor and ceil conditions

   Floor is max element ≤ target, ceil is min element ≥ target.

2. Step 2: Analyze each code snippet

   ```rust fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> { targets.iter().map(|&t| { let floor = arr.iter().filter(|&&x| x <= t).max().copied(); let ceil = arr.iter().filter(|&&x| x >= t).min().copied(); (floor, ceil) }).collect() } ``` uses filter with ≤ and ≥, then max and min respectively, which matches floor and ceil definitions. ```rust fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> { targets.iter().map(|&t| { let floor = arr.iter().filter(|&&x| x < t).max().copied(); let ceil = arr.iter().filter(|&&x| x > t).min().copied(); (floor, ceil) }).collect() } ``` uses < and > which exclude equality. ```rust fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> { targets.iter().map(|&t| { let floor = arr.iter().find(|&&x| x <= t).copied(); let ceil = arr.iter().find(|&&x| x >= t).copied(); (floor, ceil) }).collect() } ``` uses find which returns first match, not max or min. ```rust fn floor_ceil(arr: &[i32], targets: &[i32]) -> Vec<(Option<i32>, Option<i32>)> { targets.iter().map(|&t| { let floor = arr.iter().filter(|&&x| x <= t).min().copied(); let ceil = arr.iter().filter(|&&x| x >= t).max().copied(); (floor, ceil) }).collect() } ``` reverses min and max causing wrong results.

3. Final Answer:

   filter(|&&x| x <= t).max() for floor, filter(|&&x| x >= t).min() for ceil -> Option D

4. Quick Check:

   Floor = max ≤ target, Ceil = min ≥ target [OK]

Hint: Floor uses max ≤ target, ceil uses min ≥ target filters [OK]

Common Mistakes:

• Using strict < or > instead of ≤ or ≥
• Using find instead of max/min for floor/ceil
• Swapping min and max in floor/ceil logic