Floor and Ceil in Sorted Array in DSA C - Build from Scratch

Floor and Ceil in Sorted Array

📖 Scenario: You have a sorted list of numbers representing the heights of buildings in a city skyline. You want to find the closest building height that is just smaller or equal (floor) and just greater or equal (ceil) to a given target height.

🎯 Goal: Build a program that finds the floor and ceil values for a target height in a sorted array of building heights.

📋 What You'll Learn

Create an integer array called heights with exactly these values: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

Create an integer variable called target and set it to 20

Write a function called find_floor_ceil that takes the array heights, its size, the target, and two pointers *floor and *ceil to store the results

Print the floor and ceil values found for the target

💡 Why This Matters

🌍 Real World

Finding floor and ceil values is useful in many real-world tasks like price filtering, nearest neighbor search, and range queries.

💼 Career

Understanding floor and ceil operations helps in algorithm design, coding interviews, and working with sorted data efficiently.

1

Create the sorted array of building heights

Create an integer array called heights with these exact values: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91

DSA C

# Create the array heights with the given values
# Your code here

Hint

Use int heights[] = { ... }; with the exact numbers inside the braces.

2

Set the target height to find floor and ceil for

Create an integer variable called target and set it to 20

DSA C

int heights[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
# Create the integer variable target and set it to 20
# Your code here

Hint

Use int target = 20; to create the variable.

3

Write the function to find floor and ceil

Write a function called find_floor_ceil that takes the array heights, its size, the target, and two pointers *floor and *ceil. Use a loop to find the floor and ceil values for the target in the sorted array.

DSA C

int heights[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 20;

// Write the function find_floor_ceil here
// Your code here

Hint

Initialize floor and ceil to -1. Loop through the array. Update floor if element is less than target. Update ceil and return when element is greater than target. If element equals target, set both floor and ceil to it and return.

4

Print the floor and ceil values for the target

Declare two integer variables floor and ceil. Call find_floor_ceil with heights, its size, target, and addresses of floor and ceil. Then print the floor and ceil values using printf exactly as: Floor: X, Ceil: Y where X and Y are the found values.

DSA C

int heights[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 20;

void find_floor_ceil(int arr[], int size, int target, int *floor, int *ceil) {
    *floor = -1;
    *ceil = -1;
    for (int i = 0; i  target) {
            *ceil = arr[i];
            return;
        }
    }
}

// Declare floor and ceil variables, call find_floor_ceil, and print the results
# Your code here

Hint

Declare int floor, ceil;. Call find_floor_ceil(heights, 10, target, &floor, &ceil);. Use printf("Floor: %d, Ceil: %d\n", floor, ceil); to print.

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