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.