Find Ceil of an element in a Sorted Array

Question:

You are given an array and a key. You need to return the Ceil of that element.

What is Ceil?

If you are given a number say “5.8”, the floor of that number is 5 and ceil is 6.

What will be the Ceil in this question?

array = {1, 2, 3, 4, 6, 7, 8, 9};

Key = 5;

In the above array, the element 5 is not present. But we need to find the Ceil of 5. The floor of 5 is 6.

So we can define Ceil is the smallest element greater than the given key.

So according to the above definition, the smallest element greater than 5 is 6.

We can solve this question by binary search.

When we get the mid element, we check if the mid element is equal to key. If equal then return.

Else, we need to move right half or left half.

When moving left side of the array, we save the element at that index and move to left half.

Else, we move to right half directly.

Solution in C++

#include <iostream>
using namespace std;

int ceil = -1;
int get_floor(int arr[], int length, int key)
{
    int start = 0;
    int end = length - 1;

    while (start <= end)
    {

        int mid = (start + end) / 2;

        if (arr[mid] == key)
            return arr[mid];

        // return mid-1 if arr[mid - 1] is equal to key
        else if (key < arr[mid])
        {
            ceil = arr[mid];
            end = mid - 1;
        }

        else
        {
            start = mid + 1;
        }
    }

    return ceil;
}


int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 6, 7, 8, 9}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int key = 5;

    int result = get_floor(arr, size, key);

    cout<<" The floor of "<< key <<" is " <<result<<endl;

    return 0; 
} 

Output:

The floor of 5 is 6