Home » Algorithms

Floor and ceil of an element in an array using C++

In this tutorial, we will learn how to find floor and ceil of an element in an array using C++? By Radib Kar Last updated : August 10, 2023

Here, we will be searching the floor and ceil of an element from an array. A ceil is the one that is the closest greater number from the array for the element. A floor is the one that is the closest lesser number from the array for the element.

We can solve this method with both linear & binary search.

By using linear search

Initialize ceil with some largest integer (INT_MAX) & floor with some smallest integer (INT_MIN).

We can iterate through the array and check if the element is greater than the element & less than the current ceil value, we can update the ceiling value. Similarly, check if the element is lesser than the element & greater than the current floor value, we can update the floor value.

By using binary search

While doing the normal binary search keep updating the current floor & ceil value with the pivot element (arr[mid]) as per possibility.

C++ program to find floor and ceil of an array element

#include <bits/stdc++.h>
using namespace std;

//print ceil & floor for the number
void ceilandfloorLinear(vector<int>& arr, int k)
{

    cout << "..............Using linear search......\n";
    //find the closest greater than number & closet lesser number
    int _ceil = INT_MAX;
    int _floor = INT_MIN;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] > k && _ceil > arr[i])
            _ceil = arr[i];

        if (arr[i] < k && _floor < arr[i])
            _floor = arr[i];
    }

    if (_ceil != INT_MAX)
        cout << "ceiling of " << k << " is: " << _ceil << "\n";
    else
        cout << "There is no ceiling of " << k << "\n";

    if (_floor != INT_MIN)
        cout << "floor of " << k << " is: " << _floor << "\n";
    else
        cout << "There is no floor of " << k << "\n";
}

void ceilandfloorBinary(vector<int>& arr, int k)
{

    cout << "..............Using binary search......\n";
    //find the closest greater than number & closet lesser number
    int _ceil = INT_MAX;
    int _floor = INT_MIN;

    sort(arr.begin(), arr.end());

    int low = 0, high = arr.size() - 1;

    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (arr[mid] == k) {
            _ceil = k;
            _floor = k;
            break;
        }
        else if (arr[mid] > k) {
            _ceil = arr[mid];
            high = mid - 1;
        }
        else {
            _floor = arr[mid];
            low = mid + 1;
        }
    }

    if (_ceil != INT_MAX)
        cout << "ceiling of " << k << " is: " << _ceil << "\n";
    else
        cout << "There is no ceiling of " << k << "\n";

    if (_floor != INT_MIN)
        cout << "floor of " << k << " is: " << _floor << "\n";
    else
        cout << "There is no floor of " << k << "\n";
}

int main()
{
    cout << "Enter number of elements\n";
    int n;
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements\n";

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    cout << "Enter the number for which you need ceil & floor\n";
    int k;
    cin >> k;
    //using linear search
    ceilandfloorLinear(arr, k);
    //using binary search
    ceilandfloorBinary(arr, k);

    return 0;
}

Output

Enter number of elements
7
Enter the elements
56
32
87
66
12
59
33
Enter the number for which you need ceil & floor
20
..............Using linear search......
ceiling of 20 is: 32
floor of 20 is: 12
..............Using binary search......
ceiling of 20 is: 32
floor of 20 is: 12