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

Challenge - 5 Problems

❓ Predict Output

intermediate

Find floor and ceil for a target in a sorted array

What is the output of the following Rust code that finds the floor and ceil of a target value in a sorted array?

DSA Rust

fn floor_ceil(arr: &[i32], target: i32) -> (Option<i32>, Option<i32>) {
    let mut floor = None;
    let mut ceil = None;
    for &num in arr {
        if num <= target {
            floor = Some(num);
        }
        if num >= target && ceil.is_none() {
            ceil = Some(num);
        }
    }
    (floor, ceil)
}

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

A Floor: Some(3), Ceil: Some(5)

B Floor: Some(7), Ceil: Some(9)

C Floor: Some(5), Ceil: Some(7)

D Floor: None, Ceil: Some(1)

💡 Hint

Remember floor is the greatest element less than or equal to target, ceil is the smallest element greater than or equal to target.

The code iterates through the sorted array. It updates floor whenever it finds a number less than or equal to the target, so floor ends at 5. It sets ceil the first time it finds a number greater than or equal to the target, which is 7.

🧠 Conceptual

intermediate

Understanding floor and ceil in sorted arrays

In a sorted array, what does the 'floor' of a target value represent?

A The smallest element strictly greater than the target

B The smallest element greater than or equal to the target

C The element exactly equal to the target

D The largest element less than or equal to the target

💡 Hint

Floor is about the closest smaller or equal value to the target.

Floor is defined as the greatest element in the array that is less than or equal to the target value.

❓ Predict Output

advanced

Output of binary search based floor and ceil function

What is the output of this Rust code that uses binary search to find floor and ceil in a sorted array?

DSA Rust

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

fn main() {
    let arr = [2, 4, 6, 8, 10];
    let target = 5;
    let (floor, ceil) = floor_ceil_binary_search(&arr, target);
    println!("Floor: {:?}, Ceil: {:?}", floor, ceil);
}

A Floor: Some(4), Ceil: Some(6)

B Floor: Some(2), Ceil: Some(4)

C Floor: None, Ceil: Some(2)

D Floor: Some(6), Ceil: Some(8)

💡 Hint

Binary search narrows down the position where target would be inserted.

The binary search finds the position where 5 would be inserted. The floor is the element before that position (4), and the ceil is the element at that position (6).

🔧 Debug

advanced

Identify the error in floor and ceil function

What error will this Rust code produce when trying to find floor and ceil in a sorted array?

DSA Rust

fn floor_ceil_bug(arr: &[i32], target: i32) -> (Option<i32>, Option<i32>) {
    let mut floor = None;
    let mut ceil = None;
    for &num in arr {
        if num < target {
            floor = Some(num);
        }
        if num > target {
            ceil = Some(num);
            break;
        }
    }
    (floor, ceil)
}

fn main() {
    let arr = [1, 3, 5, 7];
    let target = 3;
    let (floor, ceil) = floor_ceil_bug(&arr, target);
    println!("Floor: {:?}, Ceil: {:?}", floor, ceil);
}

A Floor: Some(1), Ceil: Some(5)

B Floor: Some(3), Ceil: None

C Floor: None, Ceil: Some(3)

D Floor: Some(3), Ceil: Some(5)

💡 Hint

Check how the code handles elements equal to the target.

The code only updates floor if num < target, so it skips 3 for floor. It sets ceil at first num > target, which is 5. So floor is 1, ceil is 5.

🚀 Application

expert

Number of elements between floor and ceil inclusive

Given a sorted array and a target, how many elements are between the floor and ceil of the target (inclusive)? Consider the array [1, 2, 4, 6, 8] and target 5.

DSA Rust

fn count_between_floor_ceil(arr: &[i32], target: i32) -> usize {
    let mut floor_idx = None;
    let mut ceil_idx = None;
    for (i, &num) in arr.iter().enumerate() {
        if num <= target {
            floor_idx = Some(i);
        }
        if num >= target && ceil_idx.is_none() {
            ceil_idx = Some(i);
        }
    }
    match (floor_idx, ceil_idx) {
        (Some(f), Some(c)) => c - f + 1,
        _ => 0,
    }
}

fn main() {
    let arr = [1, 2, 4, 6, 8];
    let target = 5;
    let count = count_between_floor_ceil(&arr, target);
    println!("Count: {}", count);
}

A 3

B 2

C 4

D 1

💡 Hint

Count elements from floor index to ceil index inclusive.

Floor is 4 at index 2, ceil is 6 at index 3, so count is 3 - 2 + 1 = 2 elements. But check carefully: elements are 4 and 6 only, so count is 2.

Wait, the code counts inclusive indices, so 3 - 2 + 1 = 2 elements.

Re-examining the code and array: floor index = 2 (value 4), ceil index = 3 (value 6), count = 2.

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