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.

Categories
Relative Post