Given an unsorted array arr[] and an element x, find floor and ceiling of x in arr[0..n-1].
Floor of x is the largest element which is smaller than or equal to x. Floor of x doesn’t exist if x is smaller than smallest element of arr[].
Ceil of x is the smallest element which is greater than or equal to x. Ceil of x doesn’t exist if x is greater than greatest element of arr[].
Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
x = 7
Output : Floor = 6
Ceiling = 8
Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
x = 6
Output : Floor = 6
Ceiling = 6
Input : arr[] = {5, 6, 8, 9, 6, 5, 5, 6}
x = 10
Output : Floor = 9
Ceiling doesn't exist.
- Sort input array.
- Use binary search to find floor and ceiling of x. Refer this and this for implementation of floor and ceiling in a sorted array.
C++
#include <bits/stdc++.h>
using namespace std;
vector< int > floorAndCeil(vector< int > arr, int n, int x)
{
vector< int > result(2);
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > x) {
high = mid - 1;
}
else if (arr[mid] < x) {
low = mid + 1;
}
else {
result[0] = arr[mid];
result[1] = arr[mid];
return result;
}
}
result[0] = (high == -1) ? -1 : arr[high];
result[1] = (low == arr.size()) ? -1 : arr[low];
return result;
}
int main()
{
vector< int > arr = { 5, 6, 8, 9, 6, 5, 5, 6 };
int n = arr.size();
int x = 7;
vector< int > result = floorAndCeil(arr, n, x);
cout << "floor is " << result[0] << endl;
cout << "ceil is " << result[1] << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static int [] floorAndCeil( int [] arr, int n,
int x)
{
int [] result = new int [ 2 ];
int low = 0 , high = n - 1 ;
while (low <= high) {
int mid = low + (high - low) / 2 ;
if (arr[mid] > x) {
high = mid - 1 ;
}
else if (arr[mid] < x) {
low = mid + 1 ;
}
else {
Arrays.fill(result, arr[mid]);
return result;
}
}
result[ 0 ] = (high == - 1 ) ? - 1 : arr[high];
result[ 1 ] = (low == arr.length) ? - 1 : arr[low];
return result;
}
public static void main(String[] args)
{
int [] arr = { 5 , 6 , 8 , 9 , 6 , 5 , 5 , 6 };
int n = arr.length;
int x = 7 ;
int [] result = floorAndCeil(arr, n, x);
System.out.println( "floor is " + result[ 0 ]);
System.out.println( "ceil is " + result[ 1 ]);
}
}
|
Python3
def floor_and_ceil(arr, n, x):
result = [ 0 , 0 ]
low = 0
high = n - 1
while low < = high:
mid = low + (high - low) / / 2
if arr[mid] > x:
high = mid - 1
elif arr[mid] < x:
low = mid + 1
else :
result = [arr[mid], arr[mid]]
return result
result[ 0 ] = - 1 if high = = - 1 else arr[high]
result[ 1 ] = - 1 if low = = n else arr[low]
return result
if __name__ = = '__main__' :
arr = [ 5 , 6 , 8 , 9 , 6 , 5 , 5 , 6 ]
n = len (arr)
x = 7
result = floor_and_ceil(arr, n, x)
print ( "floor is" , result[ 0 ])
print ( "ceil is" , result[ 1 ])
|
C#
using System;
public class GFG {
public static int [] floorAndCeil( int [] arr, int n,
int x)
{
int [] result = new int [2];
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] > x) {
high = mid - 1;
}
else if (arr[mid] < x) {
low = mid + 1;
}
else {
result[0] = arr[mid];
result[1] = arr[mid];
return result;
}
}
result[0] = (high == -1) ? -1 : arr[high];
result[1] = (low == arr.Length) ? -1 : arr[low];
return result;
}
static public void Main()
{
int [] arr = { 5, 6, 8, 9, 6, 5, 5, 6 };
int n = arr.Length;
int x = 7;
int [] result = floorAndCeil(arr, n, x);
Console.WriteLine( "floor is " + result[0]);
Console.WriteLine( "ceil is " + result[1]);
}
}
|
Javascript
function floorAndCeil(arr, n, x) {
let result = [0, 0];
let low = 0;
let high = n - 1;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
if (arr[mid] > x) {
high = mid - 1;
} else if (arr[mid] < x) {
low = mid + 1;
} else {
result = [arr[mid], arr[mid]];
return result;
}
}
result[0] = (high == -1) ? -1 : arr[high];
result[1] = (low == n) ? -1 : arr[low];
return result;
}
let arr = [5, 6, 8, 9, 6, 5, 5, 6];
let n = arr.length;
let x = 7;
let result = floorAndCeil(arr, n, x);
console.log( 'floor is ' +result[0]);
console.log( 'ceil is ' +result[1]);
|
Output
floor is 6
ceil is 8
Time Complexity : O(n log n)
Auxiliary Space : O(1)
This solution is works well if there are multiple queries of floor and ceiling on a static array. We can sort the array once and answer the queries in O(Log n) time.
Method 2 (Use Linear Search:
The idea is to traverse array and keep track of two distances with respect to x.
- Minimum distance of element greater than or equal to x.
- Minimum distance of element smaller than or equal to x.
Finally print elements with minimum distances.
C++
#include<bits/stdc++.h>
using namespace std;
void floorAndCeil( int arr[], int n, int x)
{
int fInd, cInd;
int fDist = INT_MAX, cDist = INT_MAX;
for ( int i=0; i<n; i++)
{
if (arr[i] >= x && cDist > (arr[i] - x))
{
cInd = i;
cDist = arr[i] - x;
}
if (arr[i] <= x && fDist > (x - arr[i]))
{
fInd = i;
fDist = x - arr[i];
}
}
if (fDist == INT_MAX)
cout << "Floor doesn't exist " << endl;
else
cout << "Floor is " << arr[fInd] << endl;
if (cDist == INT_MAX)
cout << "Ceil doesn't exist " << endl;
else
cout << "Ceil is " << arr[cInd] << endl;
}
int main()
{
int arr[] = {5, 6, 8, 9, 6, 5, 5, 6};
int n = sizeof (arr)/ sizeof ( int );
int x = 7;
floorAndCeil(arr, n, x);
return 0;
}
|
Java
import java.io.*;
class GFG
{
public static void floorAndCeil( int arr[], int x)
{
int n = arr.length;
int fInd = - 1 , cInd = - 1 ;
int fDist = Integer.MAX_VALUE, cDist = Integer.MAX_VALUE;
for ( int i = 0 ; i < n; i++)
{
if (arr[i] >= x && cDist > (arr[i] - x))
{
cInd = i;
cDist = arr[i] - x;
}
if (arr[i] <= x && fDist > (x - arr[i]))
{
fInd = i;
fDist = x - arr[i];
}
}
if (fDist == Integer.MAX_VALUE)
System.out.println( "Floor doesn't exist " );
else
System.out.println( "Floor is " + arr[fInd]);
if (cDist == Integer.MAX_VALUE)
System.out.println( "Ceil doesn't exist " );
else
System.out.println( "Ceil is " + arr[cInd]);
}
public static void main (String[] args)
{
int arr[] = { 5 , 6 , 8 , 9 , 6 , 5 , 5 , 6 };
int x = 7 ;
floorAndCeil(arr, x);
}
}
|
Python 3
import sys
def floorAndCeil(arr, n, x):
fDist = sys.maxsize
cDist = sys.maxsize
for i in range (n):
if (arr[i] > = x and
cDist > (arr[i] - x)):
cInd = i
cDist = arr[i] - x
if (arr[i] < = x and fDist > (x - arr[i])):
fInd = i
fDist = x - arr[i]
if (fDist = = sys.maxsize):
print ( "Floor doesn't exist " )
else :
print ( "Floor is " + str (arr[fInd]))
if (cDist = = sys.maxsize):
print ( "Ceil doesn't exist " )
else :
print ( "Ceil is " + str (arr[cInd]))
if __name__ = = "__main__" :
arr = [ 5 , 6 , 8 , 9 , 6 , 5 , 5 , 6 ]
n = len (arr)
x = 7
floorAndCeil(arr, n, x)
|
C#
using System;
class GFG {
public static void floorAndCeil( int []arr, int x)
{
int n = arr.Length;
int fInd = -1, cInd = -1;
int fDist = int .MaxValue,
cDist = int .MaxValue;
for ( int i = 0; i < n; i++)
{
if (arr[i] >= x && cDist > (arr[i] - x))
{
cInd = i;
cDist = arr[i] - x;
}
if (arr[i] <= x && fDist > (x - arr[i]))
{
fInd = i;
fDist = x - arr[i];
}
}
if (fDist == int .MaxValue)
Console.Write( "Floor doesn't exist " );
else
Console.WriteLine( "Floor is " + arr[fInd]);
if (cDist == int .MaxValue)
Console.Write( "Ceil doesn't exist " );
else
Console.Write( "Ceil is " + arr[cInd]);
}
public static void Main ()
{
int []arr = {5, 6, 8, 9, 6, 5, 5, 6};
int x = 7;
floorAndCeil(arr, x);
}
}
|
PHP
<?php
function floorAndCeil( $arr ,
$n , $x )
{
$fInd = 0;
$cInd = 0;
$fDist = 999999;
$cDist = 999999;
for ( $i = 0; $i < $n ; $i ++)
{
if ( $arr [ $i ] >= $x &&
$cDist > ( $arr [ $i ] - $x ))
{
$cInd = $i ;
$cDist = $arr [ $i ] - $x ;
}
if ( $arr [ $i ] <= $x &&
$fDist > ( $x - $arr [ $i ]))
{
$fInd = $i ;
$fDist = $x - $arr [ $i ];
}
}
if ( $fDist == 999999)
echo "Floor doesn't " .
"exist " . "\n" ;
else
echo "Floor is " .
$arr [ $fInd ] . "\n" ;
if ( $cDist == 999999)
echo "Ceil doesn't " .
"exist " . "\n" ;
else
echo "Ceil is " .
$arr [ $cInd ] . "\n" ;
}
$arr = array (5, 6, 8, 9,
6, 5, 5, 6);
$n = count ( $arr );
$x = 7;
floorAndCeil( $arr , $n , $x );
?>
|
Javascript
<script>
function floorAndCeil(arr,x)
{
let n = arr.length;
let fInd = -1, cInd = -1;
let fDist = Number.MAX_VALUE, cDist = Number.MAX_VALUE;
for (let i = 0; i < n; i++)
{
if (arr[i] >= x && cDist > (arr[i] - x))
{
cInd = i;
cDist = arr[i] - x;
}
if (arr[i] <= x && fDist > (x - arr[i]))
{
fInd = i;
fDist = x - arr[i];
}
}
if (fDist == Number.MAX_VALUE)
document.write( "Floor doesn't exist <br>" );
else
document.write( "Floor is " + arr[fInd]+ "<br>" );
if (cDist == Number.MAX_VALUE)
document.write( "Ceil doesn't exist <br>" );
else
document.write( "Ceil is " + arr[cInd]+ "<br>" );
}
let arr=[5, 6, 8, 9, 6, 5, 5, 6];
let x = 7;
floorAndCeil(arr, x);
</script>
|
Output
Floor is 6
Ceil is 8
Time Complexity : O(n)
Auxiliary Space : O(1)