Floor and Ceil in Sorted Array in DSA C

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: ?
Ceil: ?

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
low=0, high=4

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

Step 2: Calculate mid=2, check value=5

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

Why: Mid helps us split the array to narrow down floor and ceil

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

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

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

Step 4: Calculate mid=3, check value=7

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

Why: Check middle of right half to find ceil candidate

Step 5: 7 > 6, update ceil=7, move high to mid-1=2

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

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

Result:

Floor: 5
Ceil: 7
Array state unchanged: [1] -> [3] -> [5] -> [7] -> [9] -> null

Annotated Code

DSA C

#include <stdio.h>

// Function to find floor and ceil in sorted array
void findFloorCeil(int arr[], int n, int target, int *floor, int *ceil) {
    int low = 0, high = n - 1;
    *floor = -1; // -1 means no floor found yet
    *ceil = -1;  // -1 means no ceil found yet

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            *floor = arr[mid];
            *ceil = arr[mid];
            return; // exact match found
        } else if (arr[mid] < target) {
            *floor = arr[mid];
            low = mid + 1; // search right side
        } else {
            *ceil = arr[mid];
            high = mid - 1; // search left side
        }
    }
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    int floor, ceil;

    findFloorCeil(arr, n, target, &floor, &ceil);

    printf("Floor: %d\n", floor);
    printf("Ceil: %d\n", ceil);

    return 0;
}

while (low <= high) {

loop to narrow search range until low passes high

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

calculate middle index to split array

if (arr[mid] == target) {

check if exact match found, then floor and ceil are target

*floor = arr[mid];

update floor when arr[mid] <= target

low = mid + 1;

move low pointer right to search for closer floor

*ceil = arr[mid];

update ceil when arr[mid] >= target

high = mid - 1;

move high pointer left to search for closer ceil

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: Compared to linear search O(n), binary search is much faster on sorted arrays

Edge Cases

target smaller than all elements

floor remains -1 (no floor), ceil is first element

DSA C

*floor = -1; // -1 means no floor found yet

target larger than all elements

ceil remains -1 (no ceil), floor is last element

DSA C

*ceil = -1;  // -1 means no ceil found yet

target exactly matches an element

floor and ceil both equal target element

DSA C

if (arr[mid] == target) { *floor = arr[mid]; *ceil = arr[mid]; return; }

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 correctly when moving pointers
Fix: Always update floor when arr[mid] < target and ceil when arr[mid] > target before moving pointers

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 quick lookup of nearest values around a target in sorted data.

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

Practice

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

easy

A. The smallest element strictly less than the number

B. The smallest element greater than or equal to the number

C. The average of all elements less than the number

D. The greatest element less 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 D

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is strictly less than number
• Mixing floor with average or median

2. Which of the following is the correct C syntax to find the middle index in binary search for array of size n?

easy

A. int mid = (0 + n) / 2;

B. int mid = 0 + n - 1 / 2;

C. int mid = (0 + (n - 1)) >> 1;

D. int mid = n / 2;

Solution

1. Step 1: Understand middle index calculation in binary search

   For array indices 0 to n-1, middle is (0 + n-1) / 2 or equivalent.

2. Step 2: Analyze options for correct syntax and efficiency

   int mid = (0 + (n - 1)) >> 1; uses bitwise right shift for division by 2, which is efficient and correct for integer mid calculation.

3. Final Answer:

   int mid = (0 + (n - 1)) >> 1; -> Option C

4. Quick Check:

   Mid = (start + end) >> 1 [OK]

Hint: Use (start + end) >> 1 for efficient mid calculation [OK]

Common Mistakes:

• Using n instead of n-1 as end index
• Forgetting parentheses causing wrong precedence
• Using floating division instead of integer

3. Given the sorted array arr = {1, 3, 5, 7, 9}, what is the floor of 6?

medium

A. 7

B. 5

C. 6

D. -1

Solution

1. Step 1: Identify elements less than or equal to 6

   Elements ≤ 6 are 1, 3, 5.

2. Step 2: Find greatest among these

   The greatest element ≤ 6 is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Floor(6) = 5 [OK]

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

Common Mistakes:

• Choosing 7 which is greater than 6
• Assuming floor equals the number if not present
• Returning -1 incorrectly when floor exists

4. Consider this code snippet to find ceil in a sorted array int ceil = -1; for(int i=0; i= x) { ceil = arr[i]; break; } }. What is the main issue?

medium

A. It may return wrong value if array is not sorted

B. It does not handle empty array

C. It returns first element ≥ x, which is correct for ceil

D. It finds floor instead of ceil

Solution

1. Step 1: Understand the code logic

   The code returns the first element in array ≥ x, which is correct if array is sorted.

2. Step 2: Identify assumptions and issues

   If array is not sorted, first element ≥ x may not be the smallest such element, so ceil is incorrect.

3. Final Answer:

   It may return wrong value if array is not sorted -> Option A

4. Quick Check:

   Ceil requires sorted array for correctness [OK]

Hint: Ceil logic needs sorted array to work correctly [OK]

Common Mistakes:

• Ignoring array sorting requirement
• Confusing ceil with floor
• Not checking for empty array before loop

5. You have a sorted array arr = {2, 4, 6, 8, 10}. If you want to find the ceil of 11 using binary search, what should be the returned value?

hard

A. -1

B. 11

C. 10

D. Error

Solution

1. Step 1: Understand ceil definition and array elements

   Ceil is smallest element ≥ target. Here, target is 11, which is greater than all elements.

2. Step 2: Check if any element ≥ 11 exists

   No element in array ≥ 11, so ceil does not exist, return -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   No element ≥ 11 means ceil = -1 [OK]

Hint: If target > max element, ceil is -1 (not found) [OK]

Common Mistakes:

• Returning last element as ceil incorrectly
• Returning target itself if not found
• Not handling no ceil case properly