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. The floor is the stone you stand on or the closest one behind you, and the ceil is the stone you stand on or the closest one ahead.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: closest ≤ 6
Ceil: closest ≥ 6

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target: 6

Goal: Find floor and ceil values for target 6 in the sorted array

Step 1: Start binary search with low=0, high=4

[1, 3, 5, 7, 9], target=6, low=0, high=4

Why: We use binary search to efficiently find floor and ceil in sorted array

Step 2: Calculate mid=2, check array[mid]=5

[1, 3, 5, 7, 9], mid=2 -> 5

Why: 5 is less than target 6, so floor could be 5, move low to mid+1=3

Step 3: Update low=3, high=4, calculate mid=3, check array[mid]=7

[1, 3, 5, 7, 9], mid=3 -> 7

Why: 7 is greater than target 6, so ceil could be 7, move high to mid-1=2

Step 4: Now low=3, high=2, loop ends

[1, 3, 5, 7, 9], low=3, high=2

Why: Search ends when low > high; floor is last smaller or equal, ceil is last greater or equal found

Result:

Floor = 5
Ceil = 7

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <optional>

using namespace std;

// Function to find floor and ceil in sorted array
pair<optional<int>, optional<int>> floorAndCeil(const vector<int>& arr, int target) {
    int low = 0, high = (int)arr.size() - 1;
    optional<int> floorVal = nullopt;
    optional<int> ceilVal = nullopt;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            // Exact match is both floor and ceil
            return {arr[mid], arr[mid]};
        } else if (arr[mid] < target) {
            floorVal = arr[mid]; // arr[mid] could be floor
            low = mid + 1;       // search right side for closer floor
        } else {
            ceilVal = arr[mid];  // arr[mid] could be ceil
            high = mid - 1;      // search left side for closer ceil
        }
    }
    return {floorVal, ceilVal};
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9};
    int target = 6;
    auto [floorVal, ceilVal] = floorAndCeil(arr, target);

    cout << "Floor = ";
    if (floorVal.has_value()) cout << floorVal.value() << "\n";
    else cout << "None\n";

    cout << "Ceil = ";
    if (ceilVal.has_value()) cout << ceilVal.value() << "\n";
    else cout << "None\n";

    return 0;
}

while (low <= high) {

loop until search space is exhausted

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

calculate middle index to split search space

if (arr[mid] == target) { return {arr[mid], arr[mid]}; }

exact match found, floor and ceil are target

else if (arr[mid] < target) { floorVal = arr[mid]; low = mid + 1; }

arr[mid] less than target, update floor and search right side

else { ceilVal = arr[mid]; high = mid - 1; }

arr[mid] greater than target, update ceil and search left side

Output

Floor = 5

Ceil = 7

Complexity Analysis

Time: O(log n) because binary search splits the array in half each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive linear search takes O(n) by scanning all elements, binary search is faster for sorted arrays

Edge Cases

target smaller than all elements

floor is None, ceil is the smallest element

DSA C++

optional<int> floorVal = nullopt;

target larger than all elements

floor is the largest element, ceil is None

DSA C++

optional<int> ceilVal = nullopt;

target exactly matches an element

floor and ceil both equal target

DSA C++

if (arr[mid] == target) { return {arr[mid], arr[mid]}; }

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 search boundaries
Fix: Assign floorVal when arr[mid] < target and ceilVal when arr[mid] > target before changing low or high

Mistake: Returning floor or ceil without checking if they exist (nullopt)
Fix: Use optional type and check if value exists before printing or using

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 to quickly find bounds around a target number in a sorted list.

The key is to use binary search to update floor and ceil candidates while narrowing the search.

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