Floor and Ceil Value

Floor and Ceil Value: 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.
Submitted by Divyansh Jaipuriyar, on August 20, 2020

Problem statement:

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.

Problem description:

The problem wants you to use the knowledge of mathematics as the floor is the value which is the largest integer less than or equal to x and ceil value is the smallest greater than or equal to x. We are required to approach the problem in a way such that the time complexity should change to linear to logarithmic.

Input:

The first line of the input is the T number of test cases. Each test case consists of integer n and x, size of the array, and the element whose floor and ceil value is to be evaluated respectively. Then each of the following lines contains n elements.

Output:

Print the floor and ceil value of the element x.

Examples:

Input:
T=1
N=5,X=3
1,2,4,5,6

Output:
floor: 2 
ceil: 4

Solution approach:

(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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.