Floor and Ceil in Sorted Array in DSA Rust - Execution Trace

Concept Flow - Floor and Ceil in Sorted Array

Start with sorted array and target

↓

Initialize low=0, high=array_length-1

↓

While low <= high

↓

Calculate mid = (low+high)/2

↓

Compare array[mid

↓

low=mid+1

↓

After loop ends

↓

Floor = array[high

↓

Ceil = array[low

↓

Return floor and ceil values

We use binary search to find positions where floor and ceil values lie by adjusting low and high pointers until they cross.

Execution Sample

DSA Rust

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

This Rust function finds floor and ceil of a target in a sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	Compare arr[mid] with target	Pointer Changes	Floor Candidate	Ceil Candidate	Visual State
1	Initialize pointers	0	6	-	-	-	None	None	[1, 2, 4, 6, 8, 10, 12]
2	Calculate mid	0	6	3	arr[3]=6 < target=7	low = mid + 1 = 4	None	None	[1, 2, 4, 6, 8, 10, 12]
3	Calculate mid	4	6	5	arr[5]=10 > target=7	high = mid - 1 = 4	None	None	[1, 2, 4, 6, 8, 10, 12]
4	Calculate mid	4	4	4	arr[4]=8 > target=7	high = mid - 1 = 3	None	None	[1, 2, 4, 6, 8, 10, 12]
5	Loop ends (low=4 > high=3)	4	3	-	-	-	arr[3]=6	arr[4]=8	[1, 2, 4, 6, 8, 10, 12]

💡 Loop ends because low (4) > high (3); floor is arr[high]=6, ceil is arr[low]=8

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5 (final)
low	0	4	4	4	4
high	6	6	4	3	3
mid	-	3	5	4	-
floor	None	None	None	None	6
ceil	None	None	None	None	8

Key Moments - 3 Insights

Why does the loop stop when low > high?

Because when low passes high, it means we have narrowed down the search and no exact match was found. At this point, high points to the floor candidate and low points to the ceil candidate, as shown in step 5 of the execution_table.

Why do we use high as floor and low as ceil after the loop?

During the search, low moves up when arr[mid] < target, so low points to the smallest element greater or equal to target (ceil). High moves down when arr[mid] > target, so high points to the largest element less or equal to target (floor). This is confirmed in the final row of execution_table.

What if the target is smaller than all elements?

Then high becomes -1 (less than 0), so floor is None. Low stays at 0, so ceil is the first element. This is handled by the checks in the code and shown in variable_tracker for floor and ceil.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of 'high' after the operation?

A 6

B 5

C 4

D 3

💡 Hint

Check the 'Pointer Changes' and 'high' column in execution_table row for step 3.

At which step does the loop condition become false?

A Step 5

B Step 4

C Step 3

D Step 2

💡 Hint

Look at the 'Operation' and 'low' and 'high' values in execution_table rows to see when low > high.

If the target was 13 (greater than all elements), what would be the floor and ceil after the loop?

A Floor = 13, Ceil = 13

B Floor = 12, Ceil = None

C Floor = None, Ceil = 12

D Floor = None, Ceil = None

💡 Hint

Recall that floor is arr[high] if high >= 0 and ceil is arr[low] if low < length; target > all elements means low goes beyond last index.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=n-1
- While low <= high, check mid = (low+high)/2
- If arr[mid] == target, floor=ceil=arr[mid]
- If arr[mid] < target, low = mid + 1
- Else high = mid - 1
- After loop, floor = arr[high] if high >= 0 else None
- Ceil = arr[low] if low < n else None

Full Transcript

This concept shows how to find the floor and ceil of a target number in a sorted array using binary search. We start with two pointers, low at 0 and high at the last index. We calculate mid and compare the middle element with the target. If equal, both floor and ceil are that element. If the middle element is less than the target, we move low up to mid + 1. If greater, we move high down to mid - 1. We repeat until low passes high. Then, floor is the element at high if high is valid, and ceil is the element at low if low is valid. This method efficiently finds the closest smaller or equal (floor) and closest greater or equal (ceil) values to the target in the array.

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