Find Floor of an element in a Sorted Array

Question:

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

What is floor?

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

What will be the floor 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 floor of 5. The floor of 5 is 4.

So we can define floor is the greatest element smaller than the given key.

So according to the above definition, the greatest element smaller than 5 is 4.

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 right side of the array, we save the element at that index and move to right half.

Else, we move to left half directly.

Solution in C++

#include <iostream>
using namespace std;

int floor = -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])
            end = mid - 1;

        else
        {
            floor = arr[mid];
            start = mid + 1;
        }
    }

    return floor;
}


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 4