Find nearest greater and smaller element from an unsorted array (Floor and Ceil)

Find just greater and smaller element than number x from an unsorted array (Floor and Ceil)

Given an array, you have to find two numbers from an array which are just smaller than a number X and just greater than a number X.

The Floor and Ceil are the nearest integer up or down.

ALGORITHM

TIME COMPLEXITY: O(N)
SPACE COMPLEXITY: O(1)

We simply use the minimum and maximum conditions wisely.

1. Initialize two variables just_greater and just_smaller with some very large and small value respectively.

2. Loop through the array as:

  • If the array element is greater than x but smaller than just_greater then just_greater = arr[i]
  • If the array element is smaller than x but larger than just_smaller then just_smaller = arr[i]

It is simply the modification of finding the second minimum and maximum in an array with a variation of having a reference number with respect to which it is found.

Ceil is number just greater than x and
Floor is number just smaller than x.

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

int main()
{
	int arr[] = {-3,-4,10,0,3,-2,15,3};
	int size_of_array = sizeof(arr)/sizeof(arr[0]);
	
	//Let we want Floor and Ceil on number 0
	int x = 0;
	
	int just_greater=INT_MAX,just_smaller=INT_MIN;
	
	for(int i=0; i<size_of_array; i++)
	{
		//if element is greater than x but smaller than present just_greater
		if(arr[i] > x and arr[i] < just_greater)
			just_greater = arr[i];
			
		//if element is Smaller than x but smaller than present just_smaller
		if(arr[i] < x and just_smaller < arr[i])
			just_smaller = arr[i];
	}		
	if(just_greater != INT_MAX)
		cout << "Ceil of x is "<<just_greater<<endl;
	else
		cout<<"No Ceil of x found\n";
		
	if(just_smaller !=INT_MIN)
		cout<<"Floor of x is "<<just_smaller<<endl;
	else
		cout<<"No floor of x found\n";

		return 0;
}
Try It




Next > < Prev
Scroll to Top