Given a sorted array of integers, find the floor and ceil of given number x in it. The floor and ceil value of a number points to the largest previous or the smallest following integer respectively

(a) Brute Force Approach:

In this approach we will iterate through the array and simply find the floor and ceil of the element x in O(n) time.

The floor will the largest element smaller than or equal to element x and the ceil will be the smallest element greater than or equal to element x.

Pseudo Code:

For FLoor:
	//initialise some variable
	//floor with -1.	
	floor=-1
	//iteratively move through all 
	//element until some largest element 
	//greater than equal to x
	for i in length(arr[]):
	if(arr[i]<=x)
	floor=arr[i]//if found some element then assign.
	if(arr[i]>x)//if arr[i]>x then break.
	break
	
For Ceil:
	//initialise some variable 
	//ceil with -1.	
	ceil=-1
	//iteratively move through all 
	//elements until smallest element
	//greater than equal to x.
	for i in length(arr[]):
	if(arr[i]>=x)
	ceil=arr[i],break

Time Complexity for the above approach in the worst case is: O(n)

Space Complexity for the above approach in the worst case is: O(1)

b) Binary Search Approach:

In this approach, we will use the concept of binary search to solve the problem. We will find the mid and then recur for the left or right side of the mid index according to the comparison.

Pseudo Code:

FOR CEIL:
    start and end are the range end points.
    //initialise ceil with -1.
    ceil=-1
    CEIL(arr[],start,end):
    ->  if x is equal to mid element then return mid element.
    ->  if x is less than the mid element then ceil of the 
        element x lies in left half of the range i.e in 
        arr[start,mid], so we will change our celi value 
        to mid element and search in left half arr[start,mid-1].
    ->  if x is greater than the mid element then ceil of the 
        element x lies in the right half of the range i.e in  arr[mid+1,end].


FOR FLOOR:
    start and end are the range end points.
    //initialise floor with -1.
    floor=-1

    FLOOR(arr[],start,end):
    ->  if x is equal to mid element then return mid element
    ->  if x is less than mid element then floor lies in 
        the left half of the range i.e arr[start,mid]
    ->  if x is greater than the mid element then floor lies 
        in the right half of the range i.e 
        arr[mid,end],assign floor equal to mid.
        The floor lies in arr[mid+1,end] half.

Time Complexity for the above approach in the worst case is: O(log(n))

Space Complexity for the above approach in the worst case is: O(1)

C++ Implementation (Brute Force Approach):

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n, x;

        cout << "Enter N and X: ";
        cin >> n >> x;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll ceil, floor;

        ceil = -1;
        floor = -1;

        //iterate through all elements
        //find largest element smaller than
        //equal to x.
        for (ll i = 0; i < n; i++) {
            if (arr[i] <= x) {
                floor = arr[i];
            }
            else //if element found then break.
                break;
        }

        //iterate through all elements
        //find smallest element greater than
        //equal to x.
        for (ll i = 0; i < n; i++) {
            if (arr[i] >= x) {
                ceil = arr[i];
                break; //break since we no need to
                //find any more element as
                //array is sorted.
            }
        }
        cout << "Floor:" << floor << " ";
        cout << "Ceil:" << ceil << "\n";
    }
 
    return 0;
}

Output:

Enter number of test cases: 3
Enter N and X: 5 3
Enter array elements: 1 2 3 4 5
Floor:3 Ceil:3
Enter N and X: 6 2
Enter array elements: 1 3 3 4 5 6        
Floor:1 Ceil:3
Enter N and X: 4 7
Enter array elements: 3 6 8 8
Floor:6 Ceil:8

C++ Implementation (Binary Search Approach):

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

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n, x;

        cout << "Enter N and X: ";
        cin >> n >> x;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        ll ceil, floor;

        //initialize floor and ceil with -1.
        ceil = -1;
        floor = -1;

        //start index for binary search.
        ll l = 0;

        //end index for binary search.
        ll r = n - 1;

        //perform binary search.
        while (l <= r) {
            //mid index.
            ll mid = l + (r - l) / 2;

            //if found then assign and break.
            if (arr[mid] == x) {
                floor = arr[mid];
                break;
            }

            //if x< mid element then search
            //left half range arr[l,mid-1].
            if (arr[mid] > x) {
                r = mid - 1;
            }

            //if x> mid element then search
            //right half range arr[mid+1,r].
            if (x > arr[mid]) {
                //since we are findin floor we need
                //to update the left floor each time.
                floor = arr[mid];
                l = mid + 1;
            }
        }

        //reinitialise.
        l = 0;
        r = n - 1;

        //perform binary search again.
        while (l <= r) {
            //mid index.
            ll mid = l + (r - l) / 2;
            //if mid element equal to x
            //then break from loop.
            if (arr[mid] == x) {
                //assign ceil.
                ceil = arr[mid];
                break;
            }
            //if x<arr[mid] then search in left
            //half range [l,mid-1]
            if (arr[mid] > x) {
                //assign each time ceil value as
                //search space is reducing.
                ceil = arr[mid];
                r = mid - 1;
            }
            if (arr[mid] < x) {
                l = mid + 1;
            }
        }
        cout << "Floor:" << floor << " ";
        cout << "Ceil:" << ceil << "\n";
    }
 
    return 0;
}

Output:

Enter number of test cases: 3 
Enter N and X: 5 3
Enter array elements: 1 4 6 8 9
Floor:1 Ceil:4
Enter N and X: 6 2
Enter array elements: 1 3 4 5 6 7
Floor:1 Ceil:3
Enter N and X: 3 2
Enter array elements: 3 5 7
Floor:-1 Ceil:3