Posted on by Kalkicode
Code Array

Find floor of a number in a sorted array

The task of finding the floor of a given number in a sorted array involves identifying the largest element in the array that is less than or equal to the given number. This problem is frequently encountered in algorithms that require value comparison, particularly in situations where the array represents a range of values. In this article, we will explore how to solve this problem, outline a clear approach, mentioned a step-by-step algorithm, explain the output, analyze the time complexity, and offer concise code examples.

Problem Statement

Given a sorted array and a target number, the objective is to find the largest element in the array that is less than or equal to the given number (the floor of the number).

Example

Consider the sorted array: Array: [-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123]

For the target numbers 0, 5, 32, -4, 12, and 8, the corresponding floors are -2, 4, 21, not found, 12, and 7, respectively.

Approach to Solve the Problem

To solve this problem, we can utilize a binary search approach. We will start by initializing the left and right pointers to the beginning and end of the array, respectively. Then, we calculate the mid index and compare the value at arr[mid] with the target number. Depending on the comparison result, we adjust the left or right pointer. The result variable will store the index of the largest element less than or equal to the target number.

Pseudocode

find_floor(arr, size, number):
    result = -1
    left = 0
    right = size - 1
    
    while left <= right:
        mid = (left + right) / 2
        if arr[mid] > number:
            right = mid - 1
        else if arr[mid] < number:
            result = mid
            left = mid + 1
        else:
            result = mid
            break
    
    if result == -1:
        print("Floor of number", number, "does not exist")
    else:
        print("Floor of number", number, "is", arr[result])

Algorithm Explanation

  1. Initialize the left and right pointers.
  2. Enter a loop as long as left is less than or equal to right.
  3. Calculate the mid index.
  4. Compare the element at arr[mid] with the target number.
  5. If arr[mid] is greater than the target number, move right to mid - 1.
  6. If arr[mid] is less than the target number, update the result and move left to mid + 1.
  7. If arr[mid] is equal to the target number, update the result and exit the loop.
  8. If result remains -1, the floor does not exist; otherwise, print the floor.

Code Solution

// C Program 
// Find floor of a number in a sorted array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
// Find floor of a number in given sorted array
void find_floor(int arr[], int size, int number)
{
	//This are used to store resultant index of floor number
	int result = -1;
	//Loop controlling variables
	int mid = 0;
	int left = 0;
	int right = size - 1;
	//Find the closest smallest element in sorted array of given number
	//In given below logic are based on binary search
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arr[mid] > number)
		{
			//When find mid element is greater than given number
			right = mid - 1;
		}
		else if (arr[mid] < number)
		{
			//When get a new smallest closest element
			result = mid;
			//When calculate middle are less than given number
			left = mid + 1;
		}
		else
		{
			//When given number are exist in sorted array
			result = mid;
			break;
		}
	}
	if (result == -1)
	{
		printf("\n Floor of number %d are not exist", number);
	}
	else
	{
		printf("\n Floor of number %d is %d", number, arr[result]);
	}
}
int main()
{
	//Define an sorted array of integers
	int arr[] = {
		-3,
		-2,
		1,
		2,
		4,
		7,
		9,
		12,
		21,
		35,
		56,
		123
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	//Display array element
	printf("\n Array  :");
	display(arr, size);
	//Test
	find_floor(arr, size, 0);
	find_floor(arr, size, 5);
	find_floor(arr, size, 32);
	find_floor(arr, size, -4);
	find_floor(arr, size, 12);
	find_floor(arr, size, 8);
	return 0;
}

Output

 Array  :  -3  -2  1  2  4  7  9  12  21  35  56  123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
/*
  Java Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// Find floor of a number in given sorted array
	public void find_floor(int[] arr, int size, int number)
	{
		//This are used to store resultant index of floor number
		int result = -1;
		//Loop controlling variables
		int mid = 0;
		int left = 0;
		int right = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (arr[mid] > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr[mid] < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		if (result == -1)
		{
			System.out.print("\n Floor of number " + number + " are not exist");
		}
		else
		{
			System.out.print("\n Floor of number " + number + " is " + arr[result] + "");
		}
	}
	public static void main(String[] args)
	{
		MyArray obj = new MyArray();
		//Define an sorted array of integers
		int[] arr = {
			-3,
			-2,
			1,
			2,
			4,
			7,
			9,
			12,
			21,
			35,
			56,
			123
		};
		//Get the size of array
		int size = arr.length;
		System.out.print("\n Array :");
		obj.display(arr, size);
		//Test
		obj.find_floor(arr, size, 0);
		obj.find_floor(arr, size, 5);
		obj.find_floor(arr, size, 32);
		obj.find_floor(arr, size, -4);
		obj.find_floor(arr, size, 12);
		obj.find_floor(arr, size, 8);
	}
}

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
//Include header file
#include <iostream>

using namespace std;
/*
  C++ Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	public:
		//Function which is display array elements
		void display(int arr[], int size)
		{
			for (int i = 0; i < size; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// Find floor of a number in given sorted array
	void find_floor(int arr[], int size, int number)
	{
		//This are used to store resultant index of floor number
		int result = -1;
		//Loop controlling variables
		int mid = 0;
		int left = 0;
		int right = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (arr[mid] > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr[mid] < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		if (result == -1)
		{
			cout << "\n Floor of number " << number << " are not exist";
		}
		else
		{
			cout << "\n Floor of number " << number << " is " << arr[result] << "";
		}
	}
};
int main()
{
	MyArray obj = MyArray();
	int arr[] = {
		-3 , -2 , 1 , 2 , 4 , 7 , 9 , 12 , 21 , 35 , 56 , 123
	};
	//Get the size of array
	int size = sizeof(arr) / sizeof(arr[0]);
	cout << "\n Array :";
	obj.display(arr, size);
	//Test
	obj.find_floor(arr, size, 0);
	obj.find_floor(arr, size, 5);
	obj.find_floor(arr, size, 32);
	obj.find_floor(arr, size, -4);
	obj.find_floor(arr, size, 12);
	obj.find_floor(arr, size, 8);
	return 0;
}

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
//Include namespace system
using System;
/*
  C# Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	public void display(int[] arr, int size)
	{
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// Find floor of a number in given sorted array
	public void find_floor(int[] arr, int size, int number)
	{
		//This are used to store resultant index of floor number
		int result = -1;
		//Loop controlling variables
		int mid = 0;
		int left = 0;
		int right = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (arr[mid] > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr[mid] < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		if (result == -1)
		{
			Console.Write("\n Floor of number " + number + " are not exist");
		}
		else
		{
			Console.Write("\n Floor of number " + number + " is " + arr[result] + "");
		}
	}
	public static void Main(String[] args)
	{
		MyArray obj = new MyArray();
		int[] arr = {
			-3 , -2 , 1 , 2 , 4 , 7 , 9 , 12 , 21 , 35 , 56 , 123
		};
		//Get the size of array
		int size = arr.Length;
		Console.Write("\n Array :");
		obj.display(arr, size);
		//Test
		obj.find_floor(arr, size, 0);
		obj.find_floor(arr, size, 5);
		obj.find_floor(arr, size, 32);
		obj.find_floor(arr, size, -4);
		obj.find_floor(arr, size, 12);
		obj.find_floor(arr, size, 8);
	}
}

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
<?php
/*
  Php Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	public	function display( $arr, $size)
	{
		for ($i = 0; $i < $size; ++$i)
		{
			echo " ". $arr[$i];
		}
		echo "\n";
	}
	// Find floor of a number in given sorted array
	public	function find_floor( $arr, $size, $number)
	{
		//This are used to store resultant index of floor number
		$result = -1;
		//Loop controlling variables
		$mid = 0;
		$left = 0;
		$right = $size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while ($left <= $right)
		{
			$mid = intval(($left + $right) / 2);
			if ($arr[$mid] > $number)
			{
				//When find mid element is greater than given number
				$right = $mid - 1;
			}
			else if ($arr[$mid] < $number)
			{
				//When get a new smallest closest element
				$result = $mid;
				//When calculate middle are less than given number
				$left = $mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				$result = $mid;
				break;
			}
		}
		if ($result == -1)
		{
			echo "\n Floor of number ". $number ." are not exist";
		}
		else
		{
			echo "\n Floor of number ". $number ." is ". $arr[$result] ."";
		}
	}
}

function main()
{
	$obj = new MyArray();
	//Define an sorted array of integers
	$arr = array(-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123);
	//Get the size of array
	$size = count($arr);
	echo "\n Array :";
	$obj->display($arr, $size);
	//Test
	$obj->find_floor($arr, $size, 0);
	$obj->find_floor($arr, $size, 5);
	$obj->find_floor($arr, $size, 32);
	$obj->find_floor($arr, $size, -4);
	$obj->find_floor($arr, $size, 12);
	$obj->find_floor($arr, $size, 8);
}
main();

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
/*
  Node Js Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	display(arr, size)
	{
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Find floor of a number in given sorted array
	find_floor(arr, size, number)
	{
		//This are used to store resultant index of floor number
		var result = -1;
		//Loop controlling variables
		var mid = 0;
		var left = 0;
		var right = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while (left <= right)
		{
			mid = parseInt((left + right) / 2);
			if (arr[mid] > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr[mid] < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		if (result == -1)
		{
			process.stdout.write("\n Floor of number " + number + " are not exist");
		}
		else
		{
			process.stdout.write("\n Floor of number " + number + " is " + arr[result] + "");
		}
	}
}

function main()
{
	var obj = new MyArray();
	//Define an sorted array of integers
	var arr = [-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123];
	//Get the size of array
	var size = arr.length;
	process.stdout.write("\n Array :");
	obj.display(arr, size);
	//Test
	obj.find_floor(arr, size, 0);
	obj.find_floor(arr, size, 5);
	obj.find_floor(arr, size, 32);
	obj.find_floor(arr, size, -4);
	obj.find_floor(arr, size, 12);
	obj.find_floor(arr, size, 8);
}
main();

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
#   Ruby Program
#   Find floor of a number in a sorted array

class MyArray

	# Function which is display array elements
	def display(arr, size)
	
		i = 0
		while (i < size)
		
			print(" ", arr[i])
			i += 1
		end
		print("\n")
	end
	#  Find floor of a number in given sorted array
	def find_floor(arr, size, number)
	
		# This are used to store resultant index of floor number
		result = -1
		# Loop controlling variables
		mid = 0
		left = 0
		right = size - 1
		# Find the closest smallest element in sorted array of given number
		# In given below logic are based on binary search
		while (left <= right)
		
			mid = (left + right) / 2
			if (arr[mid] > number)
			
				# When find mid element is greater than given number
				right = mid - 1
			elsif(arr[mid] < number)
			
				# When get a new smallest closest element
				result = mid
				# When calculate middle are less than given number
				left = mid + 1
			else
			
				# When given number are exist in sorted array
				result = mid
				break
			end
		end
		if (result == -1)
		
			print("\n Floor of number ", number ," are not exist")
		else
		
			print("\n Floor of number ", number ," is ", arr[result] ,"")
		end
	end
end
def main()

	obj = MyArray.new()
	# Define an sorted array of integers
	arr = [-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123]
	# Get the size of array
	size = arr.length
	print("\n Array :")
	obj.display(arr, size)
	# Test
	obj.find_floor(arr, size, 0)
	obj.find_floor(arr, size, 5)
	obj.find_floor(arr, size, 32)
	obj.find_floor(arr, size, -4)
	obj.find_floor(arr, size, 12)
	obj.find_floor(arr, size, 8)
end
main()

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
#   Python 3 Program
#   Find floor of a number in a sorted array

class MyArray :
	# Function which is display array elements
	def display(self, arr, size) :
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print("\n", end = "")
	
	#  Find floor of a number in given sorted array
	def find_floor(self, arr, size, number) :
		# This are used to store resultant index of floor number
		result = -1
		# Loop controlling variables
		mid = 0
		left = 0
		right = size - 1
		# Find the closest smallest element in sorted array of given number
		# In given below logic are based on binary search
		while (left <= right) :
			mid = int((left + right) / 2)
			if (arr[mid] > number) :
				# When find mid element is greater than given number
				right = mid - 1
			
			elif(arr[mid] < number) :
				# When get a new smallest closest element
				result = mid
				# When calculate middle are less than given number
				left = mid + 1
			else :
				# When given number are exist in sorted array
				result = mid
				break
			
		
		if (result == -1) :
			print("\n Floor of number ", number ," are not exist", end = "")
		else :
			print("\n Floor of number ", number ," is ", arr[result] ,"", end = "")
		
	

def main() :
	obj = MyArray()
	# Define an sorted array of integers
	arr = [-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123]
	# Get the size of array
	size = len(arr)
	print("\n Array :", end = "")
	obj.display(arr, size)
	# Test
	obj.find_floor(arr, size, 0)
	obj.find_floor(arr, size, 5)
	obj.find_floor(arr, size, 32)
	obj.find_floor(arr, size, -4)
	obj.find_floor(arr, size, 12)
	obj.find_floor(arr, size, 8)

if __name__ == "__main__": main()

Output

 Array :  -3  -2  1  2  4  7  9  12  21  35  56  123

 Floor of number  0  is  -2
 Floor of number  5  is  4
 Floor of number  32  is  21
 Floor of number  -4  are not exist
 Floor of number  12  is  12
 Floor of number  8  is  7
import scala.util.control.Breaks._
/*
  Scala Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	def display(arr: Array[Int], size: Int): Unit = {
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Find floor of a number in given sorted array
	def find_floor(arr: Array[Int], size: Int, number: Int): Unit = {
		//This are used to store resultant index of floor number
		var result: Int = -1;
		//Loop controlling variables
		var mid: Int = 0;
		var left: Int = 0;
		var right: Int = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
      	breakable
      	{
		while (left <= right)
		{
			mid = ((left + right) / 2).toInt;
			if (arr(mid) > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr(mid) < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		}
		if (result == -1)
		{
			print("\n Floor of number " + number + " are not exist");
		}
		else
		{
			print("\n Floor of number " + number + " is " + arr(result) + "");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyArray = new MyArray();
		//Define an sorted array of integers
		var arr: Array[Int] = Array(-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123);
		//Get the size of array
		var size: Int = arr.length;
		print("\n Array :");
		obj.display(arr, size);
		//Test
		obj.find_floor(arr, size, 0);
		obj.find_floor(arr, size, 5);
		obj.find_floor(arr, size, 32);
		obj.find_floor(arr, size, -4);
		obj.find_floor(arr, size, 12);
		obj.find_floor(arr, size, 8);
	}
}

Output

 Array : -3 -2 1 2 4 7 9 12 21 35 56 123

 Floor of number 0 is -2
 Floor of number 5 is 4
 Floor of number 32 is 21
 Floor of number -4 are not exist
 Floor of number 12 is 12
 Floor of number 8 is 7
/*
  Swift Program
  Find floor of a number in a sorted array
*/
class MyArray
{
	//Function which is display array elements
	func display(_ arr: [Int], _ size: Int)
	{
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
	// Find floor of a number in given sorted array
	func find_floor(_ arr: [Int], _ size: Int, _ number: Int)
	{
		//This are used to store resultant index of floor number
		var result: Int = -1;
		//Loop controlling variables
		var mid: Int = 0;
		var left: Int = 0;
		var right: Int = size - 1;
		//Find the closest smallest element in sorted array of given number
		//In given below logic are based on binary search
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (arr[mid] > number)
			{
				//When find mid element is greater than given number
				right = mid - 1;
			}
			else if (arr[mid] < number)
			{
				//When get a new smallest closest element
				result = mid;
				//When calculate middle are less than given number
				left = mid + 1;
			}
			else
			{
				//When given number are exist in sorted array
				result = mid;
				break;
			}
		}
		if (result == -1)
		{
			print("\n Floor of number ", number ," are not exist", terminator: "");
		}
		else
		{
			print("\n Floor of number ", number ," is ", arr[result] ,"", terminator: "");
		}
	}
}
func main()
{
	let obj: MyArray = MyArray();
	//Define an sorted array of integers
	let arr: [Int] = [-3, -2, 1, 2, 4, 7, 9, 12, 21, 35, 56, 123];
	//Get the size of array
	let size: Int = arr.count;
	print("\n Array :", terminator: "");
	obj.display(arr, size);
	//Test
	obj.find_floor(arr, size, 0);
	obj.find_floor(arr, size, 5);
	obj.find_floor(arr, size, 32);
	obj.find_floor(arr, size, -4);
	obj.find_floor(arr, size, 12);
	obj.find_floor(arr, size, 8);
}
main();

Output

 Array :  -3  -2  1  2  4  7  9  12  21  35  56  123

 Floor of number  0  is  -2
 Floor of number  5  is  4
 Floor of number  32  is  21
 Floor of number  -4  are not exist
 Floor of number  12  is  12
 Floor of number  8  is  7

Time Complexity Analysis

The algorithm employs binary search, halving the search range at each iteration. Thus, it runs in logarithmic time complexity of O(log n), where n is the size of the array. This makes the algorithm efficient for large sorted arrays.

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