Find floor and ceil of a number in sorted array
Finding the floor and ceiling of a number in a sorted array is a common problem in computer science and mathematics. The floor of a number in a sorted array is the largest element that is smaller than or equal to the given number, and the ceiling is the smallest element that is greater than or equal to the given number.
Problem Statement
Given a sorted array of integers and a range of numbers, find the floor and ceiling for each number in the range.
Example
Consider the sorted array:
arr = {1, 3, 4, 6, 8, 9}
For each number in the range 0 to 10, the floor and ceiling are as follows:
- For 0: Floor = -1, Ceiling = 1
- For 1: Floor = 1, Ceiling = 1
- For 2: Floor = 1, Ceiling = 3
- For 3: Floor = 3, Ceiling = 3
- For 4: Floor = 4, Ceiling = 4
- For 5: Floor = 4, Ceiling = 6
- For 6: Floor = 6, Ceiling = 6
- For 7: Floor = 6, Ceiling = 8
- For 8: Floor = 8, Ceiling = 8
- For 9: Floor = 9, Ceiling = 9
- For 10: Floor = 9, Ceiling = -1
Idea to Solve
For each number in the range, iterate through the sorted array and find the smallest element greater than or equal to the given number (ceiling) and the largest element smaller than or equal to the given number (floor).
Pseudocode
function find_floor_ceil(arr, size, start, last):
for i from start to last:
floor = -1
ceil = arr[0]
print("Number", i, "->", end=" ")
for j from 0 to size - 1:
floor = ceil
ceil = arr[j]
if arr[j] ≥ i:
break
if ceil < i:
floor = ceil
ceil = -1
if floor = ceil:
if j = 0:
floor = -1
else:
floor = arr[j-1]
print("Ceil", ceil, "Floor", floor)
// Example usage
arr = {1, 3, 4, 6, 8, 9}
size = size(arr)
start = 0
last = 10
find_floor_ceil(arr, size, start, last)
Algorithm Explanation
- The
find_floor_ceil
function takes the sorted array, its size, and the range as parameters. - It iterates through each number in the range.
- For each number, it initializes the
floor
as-1
andceil
as the first element of the array. - It iterates through the sorted array to find the ceiling and floor for the current number.
- If the ceiling is less than the number, it means there is no ceiling, so the floor becomes the new ceiling and
ceil
is set to-1
. - If
floor
is equal toceil
, it means there is no element greater than or equal to the number, so the previous element becomes the floor. - It prints the result for each number.
Code Solution
/*
C Program
Find floor and ceil of a number in sorted array
*/
#include<stdio.h>
//Find floor and ceiling in a sorted array
void find_floor_ceil(int arr[],int size,int start,int last)
{
int floor=0,ceil=0,j=0;
for (int i = start; i <= last; ++i)
{
floor = -1;
ceil = arr[0];
printf("\nNumber %d -> ", i);
for (j = 0; j < size; ++j)
{
floor=ceil;
ceil=arr[j];
if(arr[j] >= i)
{
break;
}
}
if(ceil<i)
{
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor=ceil;
ceil=-1;
}
if(floor==ceil)
{
if(j==0)
{
floor=-1;
}
else
{
floor=arr[j-1];
}
}
printf(" : Ceil %d Floor %d",ceil,floor );
}
}
int main()
{
//Defining collection array elements
int arr[] = { 1, 5, 3, 7, 4, 6, 8, 9 };
//Get the size of array elements
int size = sizeof(arr) / sizeof(arr[0]);
//Number from 0 to 10
int start=0,last=10;
find_floor_ceil(arr,size,start,last);
return 0;
}
Output
Number 0 -> : Ceil 1 Floor -1
Number 1 -> : Ceil 1 Floor -1
Number 2 -> : Ceil 5 Floor 1
Number 3 -> : Ceil 5 Floor 1
Number 4 -> : Ceil 5 Floor 1
Number 5 -> : Ceil 5 Floor 1
Number 6 -> : Ceil 7 Floor 3
Number 7 -> : Ceil 7 Floor 3
Number 8 -> : Ceil 8 Floor 6
Number 9 -> : Ceil 9 Floor 8
Number 10 -> : Ceil -1 Floor 9
#include<iostream>
using namespace std;
/*
C++ Program
Find floor and ceil of a number in sorted array
*/
class MyArray {
public:
//Find floor and ceiling in a sorted array
void find_floor_ceil(int arr[], int size, int start, int last) {
int floor = 0, ceil = 0, j = 0;
for (int i = start; i <= last; ++i) {
floor = -1;
ceil = arr[0];
cout << "\nNumber " << i << "->";
for (j = 0; j < size; ++j) {
floor = ceil;
ceil = arr[j];
if (arr[j] >= i) {
break;
}
}
if (ceil < i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor = ceil;
ceil = -1;
}
if (floor == ceil) {
if (j == 0) {
floor = -1;
} else {
floor = arr[j - 1];
}
}
cout << " : Ceil " << ceil << " Floor " << floor;
}
}
};
int main() {
MyArray obj ;
int arr[] = {
1,
5,
3,
7,
4,
6,
8,
9
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Number from 0 to 10
int start = 0, last = 10;
obj.find_floor_ceil(arr, size, start, last);
return 0;
}
Output
Number 0-> : Ceil 1 Floor -1
Number 1-> : Ceil 1 Floor -1
Number 2-> : Ceil 5 Floor 1
Number 3-> : Ceil 5 Floor 1
Number 4-> : Ceil 5 Floor 1
Number 5-> : Ceil 5 Floor 1
Number 6-> : Ceil 7 Floor 3
Number 7-> : Ceil 7 Floor 3
Number 8-> : Ceil 8 Floor 6
Number 9-> : Ceil 9 Floor 8
Number 10-> : Ceil -1 Floor 9
/*
Java Program
Find floor and ceil of a number in sorted array
*/
public class MyArray {
//Find floor and ceiling in a sorted array
public void find_floor_ceil(int []arr,int size,int start,int last)
{
int floor=0,ceil=0,j=0;
for (int i = start; i <= last; ++i)
{
floor = -1;
ceil = arr[0];
System.out.print("\nNumber "+i+" -> ");
for (j = 0; j < size; ++j)
{
floor = ceil;
ceil = arr[j];
if(arr[j] >= i)
{
break;
}
}
if(ceil<i)
{
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor=ceil;
ceil=-1;
}
if(floor==ceil)
{
if(j==0)
{
floor=-1;
}
else
{
floor=arr[j-1];
}
}
System.out.print(" : Ceil "+ceil+" Floor "+floor );
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define array elements
int []arr = { 1, 5, 3, 7, 4, 6, 8, 9 };
//Count size of array
int size=arr.length;
//Number from 0 to 10
int start=0,last=10;
obj.find_floor_ceil(arr,size,start,last);
}
}
Output
Number 0-> : Ceil 1 Floor -1
Number 1-> : Ceil 1 Floor -1
Number 2-> : Ceil 5 Floor 1
Number 3-> : Ceil 5 Floor 1
Number 4-> : Ceil 5 Floor 1
Number 5-> : Ceil 5 Floor 1
Number 6-> : Ceil 7 Floor 3
Number 7-> : Ceil 7 Floor 3
Number 8-> : Ceil 8 Floor 6
Number 9-> : Ceil 9 Floor 8
Number 10-> : Ceil -1 Floor 9
using System;
/*
C# Program
Find floor and ceil of a number in sorted array
*/
public class MyArray {
//Find floor and ceiling in a sorted array
public void find_floor_ceil(int[] arr, int size, int start, int last) {
int floor = 0, ceil = 0, j = 0;
for (int i = start; i <= last; ++i) {
floor = -1;
ceil = arr[0];
Console.Write("\nNumber " + i + " -> ");
for (j = 0; j < size; ++j) {
floor = ceil;
ceil = arr[j];
if (arr[j] >= i) {
break;;
}
}
if (ceil < i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor = ceil;
ceil = -1;
}
if (floor == ceil) {
if (j == 0) {
floor = -1;
} else {
floor = arr[j - 1];
}
}
Console.Write(" : Ceil " + ceil + " Floor " + floor);
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Define array elements
int[] arr = {
1,
5,
3,
7,
4,
6,
8,
9
};
//Count size of array
int size = arr.Length;
//Number from 0 to 10
int start = 0, last = 10;
obj.find_floor_ceil(arr, size, start, last);
}
}
Output
Number 0 -> : Ceil 1 Floor -1
Number 1 -> : Ceil 1 Floor -1
Number 2 -> : Ceil 5 Floor 1
Number 3 -> : Ceil 5 Floor 1
Number 4 -> : Ceil 5 Floor 1
Number 5 -> : Ceil 5 Floor 1
Number 6 -> : Ceil 7 Floor 3
Number 7 -> : Ceil 7 Floor 3
Number 8 -> : Ceil 8 Floor 6
Number 9 -> : Ceil 9 Floor 8
Number 10 -> : Ceil -1 Floor 9
<?php
/*
Php Program
Find floor and ceil of a number in sorted array
*/
class MyArray {
//Find floor and ceiling in a sorted array
public function find_floor_ceil($arr, $size, $start, $last) {
$floor = 0;
$ceil = 0;
$j = 0;
for ($i = $start; $i <= $last; ++$i) {
$floor = -1;
$ceil = $arr[0];
echo("\nNumber ". $i ."->");
for ($j = 0; $j < $size; ++$j) {
$floor = $ceil;
$ceil = $arr[$j];
if ($arr[$j] >= $i) {
break;
}
}
if ($ceil < $i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
$floor = $ceil;
$ceil = -1;
}
if ($floor == $ceil) {
if ($j == 0) {
$floor = -1;
} else {
$floor = $arr[$j - 1];
}
}
echo(" : Ceil ". $ceil ." Floor ". $floor);
}
}
}
function main() {
$obj = new MyArray();
//Define array elements
$arr = array(1, 5, 3, 7, 4, 6, 8, 9);
//Count size of array
$size = count($arr);
//Number from 0 to 10
$start = 0;
$last = 10;
$obj->find_floor_ceil($arr, $size, $start, $last);
}
main();
Output
Number 0-> : Ceil 1 Floor -1
Number 1-> : Ceil 1 Floor -1
Number 2-> : Ceil 5 Floor 1
Number 3-> : Ceil 5 Floor 1
Number 4-> : Ceil 5 Floor 1
Number 5-> : Ceil 5 Floor 1
Number 6-> : Ceil 7 Floor 3
Number 7-> : Ceil 7 Floor 3
Number 8-> : Ceil 8 Floor 6
Number 9-> : Ceil 9 Floor 8
Number 10-> : Ceil -1 Floor 9
/*
Node Js Program
Find floor and ceil of a number in sorted array
*/
class MyArray {
//Find floor and ceiling in a sorted array
find_floor_ceil(arr, size, start, last) {
var floor = 0;
var ceil = 0;
var j = 0;
for (var i = start; i <= last; ++i) {
floor = -1;
ceil = arr[0];
process.stdout.write("\nNumber " + i + "->");
for (j = 0; j < size; ++j) {
floor = ceil;
ceil = arr[j];
if (arr[j] >= i) {
break;
}
}
if (ceil < i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor = ceil;
ceil = -1;
}
if (floor == ceil) {
if (j == 0) {
floor = -1;
} else {
floor = arr[j - 1];
}
}
process.stdout.write(" : Ceil " + ceil + " Floor " + floor);
}
}
}
function main(args) {
var obj = new MyArray();
//Define array elements
var arr = [1, 5, 3, 7, 4, 6, 8, 9];
//Count size of array
var size = arr.length;
//Number from 0 to 10
var start = 0;
var last = 10;
obj.find_floor_ceil(arr, size, start, last);
}
main();
Output
Number 0-> : Ceil 1 Floor -1
Number 1-> : Ceil 1 Floor -1
Number 2-> : Ceil 5 Floor 1
Number 3-> : Ceil 5 Floor 1
Number 4-> : Ceil 5 Floor 1
Number 5-> : Ceil 5 Floor 1
Number 6-> : Ceil 7 Floor 3
Number 7-> : Ceil 7 Floor 3
Number 8-> : Ceil 8 Floor 6
Number 9-> : Ceil 9 Floor 8
Number 10-> : Ceil -1 Floor 9
# Python 3 Program
# Find floor and ceil of a number in sorted array
class MyArray :
# Find floor and ceiling in a sorted array
def find_floor_ceil(self, arr, size, start, last) :
floor = 0
ceil = 0
j = 0
i = start
while (i <= last) :
floor = -1
ceil = arr[0]
print("\nNumber ", i ,"->", end = "")
j = 0
while (j < size) :
floor = ceil
ceil = arr[j]
if (arr[j] >= i) :
break
j += 1
if (ceil < i) :
# When ceil is less than number i
# then modified ceil data to floor and
# set ceil value to -1
floor = ceil
ceil = -1
if (floor == ceil) :
if (j == 0) :
floor = -1
else :
floor = arr[j - 1]
print(" : Ceil ", ceil ," Floor ", floor, end = "")
i += 1
def main() :
obj = MyArray()
arr = [1, 5, 3, 7, 4, 6, 8, 9]
size = len(arr)
start = 0
last = 10
obj.find_floor_ceil(arr, size, start, last)
if __name__ == "__main__":
main()
Output
Number 0 -> : Ceil 1 Floor -1
Number 1 -> : Ceil 1 Floor -1
Number 2 -> : Ceil 5 Floor 1
Number 3 -> : Ceil 5 Floor 1
Number 4 -> : Ceil 5 Floor 1
Number 5 -> : Ceil 5 Floor 1
Number 6 -> : Ceil 7 Floor 3
Number 7 -> : Ceil 7 Floor 3
Number 8 -> : Ceil 8 Floor 6
Number 9 -> : Ceil 9 Floor 8
Number 10 -> : Ceil -1 Floor 9
# Ruby Program
# Find floor and ceil of a number in sorted array
class MyArray
# Find floor and ceiling in a sorted array
def find_floor_ceil(arr, size, start, last)
floor = 0
ceil = 0
j = 0
i = start
while (i <= last)
floor = -1
ceil = arr[0]
print("\nNumber ", i ,"->")
j = 0
while (j < size)
floor = ceil
ceil = arr[j]
if (arr[j] >= i)
break
end
j += 1
end
if (ceil < i)
# When ceil is less than number i
# then modified ceil data to floor and
# set ceil value to -1
floor = ceil
ceil = -1
end
if (floor == ceil)
if (j == 0)
floor = -1
else
floor = arr[j - 1]
end
end
print(" :Ceil ", ceil ," Floor ", floor)
i += 1
end
end
end
def main()
obj = MyArray.new()
arr = [1, 5, 3, 7, 4, 6, 8, 9]
size = arr.length
start = 0
last = 10
obj.find_floor_ceil(arr, size, start, last)
end
main()
Output
Number 0-> :Ceil 1 Floor -1
Number 1-> :Ceil 1 Floor -1
Number 2-> :Ceil 5 Floor 1
Number 3-> :Ceil 5 Floor 1
Number 4-> :Ceil 5 Floor 1
Number 5-> :Ceil 5 Floor 1
Number 6-> :Ceil 7 Floor 3
Number 7-> :Ceil 7 Floor 3
Number 8-> :Ceil 8 Floor 6
Number 9-> :Ceil 9 Floor 8
Number 10-> :Ceil -1 Floor 9
/*
Scala Program
Find floor and ceil of a number in sorted array
*/
import scala.util.control.Breaks._
class MyArray {
//Find floor and ceiling in a sorted array
def find_floor_ceil(arr: Array[Int], size: Int, start: Int, last: Int): Unit = {
var floor: Int = 0;
var ceil: Int = 0;
var j: Int = 0;
var i: Int = start;
while (i <= last) {
floor = -1;
ceil = arr(0);
print("\nNumber " + i + "->");
j = 0;
breakable
{
while (j < size) {
floor = ceil;
ceil = arr(j);
if (arr(j) >= i) {
break;
}
j += 1;
}
}
if (ceil < i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor = ceil;
ceil = -1;
}
if (floor == ceil) {
if (j == 0) {
floor = -1;
} else {
floor = arr(j - 1);
}
}
print(" : Ceil " + ceil + " Floor " + floor);
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(1, 5, 3, 7, 4, 6, 8, 9);
val size: Int = arr.length;
val start: Int = 0;
val last: Int = 10;
obj.find_floor_ceil(arr, size, start, last);
}
}
Output
Number 0-> : Ceil 1 Floor -1
Number 1-> : Ceil 1 Floor -1
Number 2-> : Ceil 5 Floor 1
Number 3-> : Ceil 5 Floor 1
Number 4-> : Ceil 5 Floor 1
Number 5-> : Ceil 5 Floor 1
Number 6-> : Ceil 7 Floor 3
Number 7-> : Ceil 7 Floor 3
Number 8-> : Ceil 8 Floor 6
Number 9-> : Ceil 9 Floor 8
Number 10-> : Ceil -1 Floor 9
/*
Swift Program
Find floor and ceil of a number in sorted array
*/
class MyArray {
//Find floor and ceiling in a sorted array
func find_floor_ceil(_ arr: [Int], _ size: Int, _ start: Int, _ last: Int) {
var floor: Int = 0;
var ceil: Int = 0;
var j: Int = 0;
var i: Int = start;
while (i <= last) {
floor = -1;
ceil = arr[0];
print("\nNumber ", i ,"->", terminator: "");
j = 0;
while (j < size) {
floor = ceil;
ceil = arr[j];
if (arr[j] >= i) {
break;
}
j += 1;
}
if (ceil < i) {
//When ceil is less than number i
//then modified ceil data to floor and
//set ceil value to -1
floor = ceil;
ceil = -1;
}
if (floor == ceil) {
if (j == 0) {
floor = -1;
} else {
floor = arr[j - 1];
}
}
print(" : Ceil ", ceil ," Floor ", floor, terminator: "");
i += 1;
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [1, 5, 3, 7, 4, 6, 8, 9];
let size: Int = arr.count;
let start: Int = 0;
let last: Int = 10;
obj.find_floor_ceil(arr, size, start, last);
}
main();
Output
Number 0 -> : Ceil 1 Floor -1
Number 1 -> : Ceil 1 Floor -1
Number 2 -> : Ceil 5 Floor 1
Number 3 -> : Ceil 5 Floor 1
Number 4 -> : Ceil 5 Floor 1
Number 5 -> : Ceil 5 Floor 1
Number 6 -> : Ceil 7 Floor 3
Number 7 -> : Ceil 7 Floor 3
Number 8 -> : Ceil 8 Floor 6
Number 9 -> : Ceil 9 Floor 8
Number 10 -> : Ceil -1 Floor 9
Time Complexity
For each number in the range, the algorithm iterates through the sorted array once. Therefore, the time complexity of
the algorithm is O(n * m)
, where n
is the size of the sorted array and m
is
the size of the range.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment