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

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

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.

New Comment





Categories
Relative Post