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

Floor and Ceil in Sorted Array

📖 Scenario: You are working on a program that helps users find the closest values in a sorted list of numbers. This is useful in many real-life cases, like finding the nearest available price or closest date.

🎯 Goal: Build a program that finds the floor and ceil of a given number in a sorted array. The floor is the greatest number less than or equal to the target, and the ceil is the smallest number greater than or equal to the target.

📋 What You'll Learn

Create a sorted array of integers

Create a target integer to find floor and ceil for

Write logic to find floor and ceil values in the array

Print the floor and ceil values

💡 Why This Matters

🌍 Real World

Finding floor and ceil values is useful in pricing systems, date/time scheduling, and searching nearest values in sorted data.

💼 Career

Understanding floor and ceil concepts helps in algorithm design and optimization tasks common in software development and data analysis roles.

1

Create the sorted array

Create a sorted array of integers called arr with these exact values: 2, 4, 6, 8, 10, 12, 14

DSA C++

// Create the sorted array called arr
// Your code here

Hint

Use C++ array syntax with exact values in ascending order.

2

Set the target number

Create an integer variable called target and set it to 9

DSA C++

int arr[] = {2, 4, 6, 8, 10, 12, 14};
// Create the target variable called target and set it to 9
// Your code here

Hint

Use a simple integer variable assignment.

3

Find floor and ceil values

Write code to find the floor and ceil of target in arr. Use two integer variables called floor and ceil. Initialize floor to -1 and ceil to -1. Use a for loop with variable i from 0 to 6 to check each element in arr. If arr[i] is less than or equal to target, update floor to arr[i]. If arr[i] is greater than or equal to target and ceil is still -1, update ceil to arr[i].

DSA C++

int arr[] = {2, 4, 6, 8, 10, 12, 14};
int target = 9;
// Initialize floor and ceil
int floor = -1;
int ceil = -1;
// Use a for loop with i from 0 to 6 to find floor and ceil
// Your code here

Hint

Loop through the array and update floor and ceil based on conditions.

4

Print floor and ceil values

Print the floor and ceil values using std::cout in this exact format: Floor: X and Ceil: Y where X and Y are the values of floor and ceil respectively.

DSA C++

int arr[] = {2, 4, 6, 8, 10, 12, 14};
int target = 9;
int floor = -1;
int ceil = -1;
for (int i = 0; i = target && ceil == -1) {
        ceil = arr[i];
    }
}
// Print floor and ceil values
// Your code here

Hint

Use std::cout to print the values with the exact text format.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The greatest element less than or equal to the number

B. The smallest element greater than the number

C. The average of all elements less than the number

D. The smallest element less than 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. Other options describe different concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option A

4. Quick Check:

   Floor = greatest ≤ number [OK]

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

Common Mistakes:

• Confusing floor with ceil
• Choosing smallest element greater than number
• Thinking floor is average or exact match only

2. Which of the following is the correct C++ function signature to find the floor of a number in a sorted array?

easy

A. int findFloor(int arr[], int n, int x);

B. void findFloor(int arr[], int n, int x);

C. int findFloor(int arr, int n, int x);

D. int findFloor(int arr[], int x);

Solution

1. Step 1: Analyze function parameters

   The function needs the array, its size, and the target number to find floor.

2. Step 2: Check each option's signature

   int findFloor(int arr[], int n, int x); correctly uses array pointer, size, and target number. void findFloor(int arr[], int n, int x); returns void which is incorrect. int findFloor(int arr, int n, int x); uses int arr instead of array. int findFloor(int arr[], int x); misses size parameter.

3. Final Answer:

   int findFloor(int arr[], int n, int x); -> Option A

4. Quick Check:

   Correct signature includes array, size, target [OK]

Hint: Function needs array, size, and target number [OK]

Common Mistakes:

• Omitting array size parameter
• Using wrong array type
• Returning void instead of int

3. What is the output of the following code snippet?

int arr[] = {1, 3, 5, 7, 9};
int n = 5;
int x = 6;
int floor = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] <= x) floor = arr[i];
  else break;
}
std::cout << floor;

medium

A. 6

B. 7

C. 5

D. -1

Solution

1. Step 1: Trace the loop and condition

   Loop checks each element ≤ 6. Elements 1, 3, 5 satisfy condition, floor updates to 5. When arr[i] = 7, condition fails and loop breaks.

2. Step 2: Determine final floor value

   Floor remains 5 after loop ends.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Floor of 6 in array = 5 [OK]

Hint: Floor is last element ≤ target before break [OK]

Common Mistakes:

• Choosing 6 which is not in array
• Choosing 7 which is > 6
• Not updating floor correctly

4. Find the error in the following code to find the ceil of a number in a sorted array:

int findCeil(int arr[], int n, int x) {
  int ceil = -1;
  for (int i = 0; i < n; i++) {
    if (arr[i] >= x) {
      ceil = arr[i];
    }
  }
  return ceil;
}

medium

A. It uses wrong comparison operator

B. It returns -1 even if ceil exists

C. It should return floor instead of ceil

D. It does not return the smallest element ≥ x

Solution

1. Step 1: Understand the loop logic

   The loop updates ceil whenever arr[i] ≥ x, but does not stop or check for smallest such element.

2. Step 2: Identify the error

   Because it keeps updating, it ends with the last element ≥ x, not the smallest. It should break or track minimum.

3. Final Answer:

   It does not return the smallest element ≥ x -> Option D

4. Quick Check:

   Ceil = smallest ≥ x, code returns largest ≥ x [OK]

Hint: Ceil must be smallest ≥ target, not last found [OK]

Common Mistakes:

• Not breaking loop after first valid ceil
• Updating ceil without checking if smaller
• Confusing floor and ceil logic

5. Given a sorted array arr = {2, 4, 6, 8, 10}, what are the floor and ceil of x = 5? Choose the correct pair.

hard

A. Floor = 5, Ceil = 6

B. Floor = 4, Ceil = 6

C. Floor = 4, Ceil = 5

D. Floor = 6, Ceil = 8

Solution

1. Step 1: Find floor of 5 in array

   Floor is greatest element ≤ 5. Elements ≤ 5 are 2 and 4, greatest is 4.

2. Step 2: Find ceil of 5 in array

   Ceil is smallest element ≥ 5. Elements ≥ 5 are 6, 8, 10, smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option B

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ x, Ceil ≥ x; pick closest elements [OK]

Common Mistakes:

• Assuming floor or ceil must equal x
• Choosing elements not in array
• Mixing floor and ceil values