Posted on by Kalkicode
Code Array

# 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
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

1. The `find_floor_ceil` function takes the sorted array, its size, and the range as parameters.
2. It iterates through each number in the range.
3. For each number, it initializes the `floor` as `-1` and `ceil` as the first element of the array.
4. It iterates through the sorted array to find the ceiling and floor for the current number.
5. 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`.
6. If `floor` is equal to `ceil`, it means there is no element greater than or equal to the number, so the previous element becomes the floor.
7. 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;

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);

//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;
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);
//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;

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;
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;
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;
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
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
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;
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.

## Comment

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.

Categories
Relative Post