Floor and Ceil in Sorted Array in DSA Rust - Deep Dive

Overview - Floor and Ceil in Sorted Array

What is it?

Floor and Ceil in a sorted array are two special values related to a target number. The floor is the greatest number in the array that is less than or equal to the target. The ceil is the smallest number in the array that is greater than or equal to the target. These concepts help find closest matches quickly in sorted data.

Why it matters

Without floor and ceil, finding closest values in sorted data would require checking every element, which is slow. These concepts let us quickly find near matches, which is important in searching, decision making, and optimization tasks. For example, when picking a price just below or above a budget, floor and ceil help instantly.

Where it fits

Before learning floor and ceil, you should understand arrays and sorting. After this, you can learn binary search deeply and then explore range queries or interval problems that use floor and ceil concepts.

Mental Model

Core Idea

Floor and ceil find the closest smaller-or-equal and larger-or-equal values to a target in a sorted list.

Think of it like...

Imagine standing on a number line with stepping stones placed in order. The floor is the stone you can step back to without going past the target, and the ceil is the stone you can step forward to without overshooting.

Sorted Array: 1   3   5   7   9
Target: 6
Floor: 5 (largest ≤ 6)
Ceil: 7 (smallest ≥ 6)

Index:   0   1   2   3   4
Value:   1 -> 3 -> 5 -> 7 -> 9

Build-Up - 6 Steps

1

Foundation

Understanding Sorted Arrays

Concept: Learn what a sorted array is and why order matters.

A sorted array is a list of numbers arranged from smallest to largest. This order helps us find values faster because we know where to look. For example, in [1, 3, 5, 7, 9], 3 always comes before 5.

Result

You can quickly tell if a number is smaller or larger than others by its position.

Knowing the array is sorted lets us use faster search methods than checking every number.

2

Foundation

Defining Floor and Ceil Simply

Concept: Introduce floor and ceil as closest smaller-or-equal and larger-or-equal values.

Floor of a target is the biggest number in the array that is not bigger than the target. Ceil is the smallest number that is not smaller than the target. For example, floor of 6 in [1,3,5,7,9] is 5, ceil is 7.

Result

You understand floor and ceil as two sides of a target number in a sorted list.

Floor and ceil help find closest matches, which is useful in many real-world problems.

3

Intermediate

Linear Search for Floor and Ceil

🤔Before reading on: do you think checking every element or using a shortcut is faster for floor and ceil? Commit to your answer.

Concept: Find floor and ceil by checking each element one by one.

Start from the beginning of the array and move forward. Keep track of the largest number less than or equal to the target for floor. Keep track of the smallest number greater than or equal to the target for ceil. This works but can be slow for big arrays.

Result

You get correct floor and ceil but with time proportional to array size.

Linear search is simple but inefficient for large sorted arrays.

4

Intermediate

Binary Search to Find Floor and Ceil

🤔Before reading on: do you think binary search can find floor and ceil in less time than linear search? Commit to yes or no.

Concept: Use binary search to quickly find floor and ceil by dividing the search space.

Binary search splits the array in half repeatedly. If the middle number is equal to the target, floor and ceil are that number. If middle is less than target, floor could be middle or to the right. If middle is greater, ceil could be middle or to the left. Keep track of candidates while searching.

Result

Floor and ceil found in about log2(n) steps instead of n.

Binary search leverages sorting to find floor and ceil efficiently.

5

Advanced

Implementing Floor and Ceil in Rust

🤔Before reading on: do you think Rust's standard library has built-in methods for floor and ceil in slices? Commit to yes or no.

Concept: Write Rust code using binary search to find floor and ceil in a sorted slice.

Use slice.binary_search to find the target. If found, floor and ceil are the target. If not found, binary_search returns Err with insertion point. Floor is element before insertion point if exists, ceil is element at insertion point if exists. Handle edge cases when insertion point is 0 or at array end.

Result

Rust code that returns Option indices for floor and ceil or None if not found.

Understanding Rust's binary_search return type helps implement floor and ceil cleanly.

6

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think floor and ceil always exist for any target in a sorted array? Commit to yes or no.

Concept: Learn about cases when floor or ceil may not exist and how to handle them efficiently.

If target is smaller than all elements, floor does not exist (None). If target is larger than all elements, ceil does not exist. Code must check these boundaries. Also, repeated elements affect floor and ceil: floor is last occurrence ≤ target, ceil is first occurrence ≥ target. Optimizing for these cases improves robustness.

Result

Robust floor and ceil functions that handle all inputs correctly.

Knowing edge cases prevents bugs and ensures correct results in all scenarios.

Under the Hood

Binary search works by repeatedly dividing the sorted array in half and comparing the middle element to the target. It uses the sorted order to eliminate half the search space each time. The floor and ceil are found by tracking the closest smaller or equal and larger or equal elements during this process. Rust's binary_search returns a Result type that encodes whether the target was found or where it should be inserted, enabling efficient floor and ceil calculation.

Why designed this way?

Binary search was designed to speed up search in sorted data from linear time to logarithmic time. The Result type in Rust's binary_search cleanly encodes success or failure with insertion point, avoiding extra searches. This design balances speed, safety, and clarity, making floor and ceil easy to implement without scanning the whole array.

Sorted Array
┌─────────────────────────────┐
│ 1 │ 3 │ 5 │ 7 │ 9 │ 11 │ 13 │
└─────────────────────────────┘

Search target: 8

Step 1: Check middle (7) < 8 -> floor candidate = 7, search right half
Step 2: Check middle (11) > 8 -> ceil candidate = 11, search left half
Step 3: Narrow down to empty range

Result: floor = 7, ceil = 11

Myth Busters - 4 Common Misconceptions

Quick: If the target is smaller than all array elements, does floor exist? Commit yes or no.

Common Belief: Floor always exists for any target in a sorted array.

Reality: Floor does not exist if the target is smaller than the smallest element.

Why it matters: Assuming floor always exists can cause errors or crashes when accessing invalid indices.

Quick: If the target is larger than all array elements, does ceil exist? Commit yes or no.

Common Belief: Ceil always exists for any target in a sorted array.

Reality: Ceil does not exist if the target is larger than the largest element.

Why it matters: Ignoring this causes incorrect results or runtime errors when ceil is assumed present.

Quick: Does binary_search always return the exact target index? Commit yes or no.

Common Belief: binary_search returns the target index or fails without useful info.

Reality: binary_search returns Err with insertion point when target not found, which helps find floor and ceil.

Why it matters: Not using insertion point wastes the opportunity for efficient floor and ceil calculation.

Quick: If the array has duplicates, is floor always the first occurrence? Commit yes or no.

Common Belief: Floor and ceil always correspond to the first occurrence of a value.

Reality: Floor is the last occurrence ≤ target; ceil is the first occurrence ≥ target, which may differ in duplicates.

Why it matters: Misunderstanding this leads to wrong indices and unexpected behavior in presence of duplicates.

Expert Zone

1

Rust's binary_search returns a Result that encodes insertion point, enabling floor and ceil without extra scans.

2

Handling duplicates requires careful choice of floor as last ≤ target and ceil as first ≥ target to maintain correctness.

3

Edge cases where floor or ceil do not exist must be explicitly handled to avoid panics or invalid results.

When NOT to use

If the array is unsorted, floor and ceil cannot be found efficiently with binary search; use linear search or sort first. For dynamic data with frequent inserts/deletes, balanced trees or binary search trees provide better floor and ceil operations.

Production Patterns

Floor and ceil are used in database indexing to find range queries, in financial systems to find closest price points, and in scheduling to find nearest time slots. Rust implementations often wrap binary_search with helper functions returning Option types for safe use.

Connections

Binary Search

Floor and ceil use binary search as the core method to find closest values efficiently.

Understanding binary search deeply unlocks efficient floor and ceil implementations.

Interval Trees

Floor and ceil concepts extend to interval trees where closest intervals are queried.

Knowing floor and ceil helps grasp how interval trees find nearest overlapping intervals.

Decision Making in Economics

Floor and ceil relate to choosing closest acceptable options under constraints, like budgets or prices.

Recognizing floor and ceil in economic decisions shows how algorithms model real-world choices.

Common Pitfalls

#1 Assuming floor always exists and accessing array[-1] when target is smaller than all elements.

Wrong approach:

let floor = arr[insertion_point - 1]; // fails if insertion_point == 0

Correct approach:

let floor = if insertion_point > 0 { Some(arr[insertion_point - 1]) } else { None };

Root cause:

Not checking boundary conditions leads to invalid index access.

#2 Using linear search for floor and ceil on large arrays causing slow performance.

Wrong approach:

for &num in arr.iter() { if num <= target { floor = Some(num); } if num >= target && ceil.is_none() { ceil = Some(num); } }

Correct approach:

Use binary_search and insertion point to find floor and ceil in O(log n) time.

Root cause:

Ignoring sorted property wastes efficiency opportunities.

#3 Ignoring duplicates and returning first occurrence as floor even if a later occurrence is closer.

Wrong approach:

floor = arr.iter().position(|&x| x == target).unwrap();

Correct approach:

floor = arr.iter().rposition(|&x| x <= target);

Root cause:

Misunderstanding floor definition in presence of duplicates.

Key Takeaways

Floor and ceil find the closest smaller-or-equal and larger-or-equal values to a target in a sorted array.

Binary search enables efficient floor and ceil finding in logarithmic time by using insertion points.

Edge cases where floor or ceil do not exist must be handled to avoid errors.

Rust's binary_search returns a Result with insertion point, which is key to implementing floor and ceil.

Understanding duplicates and boundary conditions ensures correct and robust floor and ceil results.

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