Floor in a Sorted Array
Last Updated :
30 Oct, 2022
Given a sorted array and a value x, the floor of x is the largest element in the array smaller than or equal to x. Write efficient functions to find the floor of x
Examples:
Input: arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output: 2
Explanation: 2 is the largest element in
arr[] smaller than 5
Input: arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20
Output: 19
Explanation: 19 is the largest element in
arr[] smaller than 20
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0
Output : -1
Explanation: Since floor doesn’t exist, output is -1.
Naive Approach: To solve the problem follow the below idea:
The idea is simple, traverse through the array and find the first element greater than x. The element just before the found element is the floor of x
Follow the given steps to solve the problem:
- Traverse through the array from start to end.
- If the current element is greater than x print the previous number and break out of the loop
- If there is no number greater than x then print the last element
- If the first number is greater than x then print that the floor of x doesn’t exist
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
int floorSearch(int arr[], int n, int x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
cout << "Floor of " << x
<< " doesn't exist in array ";
else
cout << "Floor of " << x << " is " << arr[index];
return 0;
}
|
C
#include <stdio.h>
int floorSearch(int arr[], int n, int x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
printf("Floor of %d doesn't exist in array ", x);
else
printf("Floor of %d is %d", x, arr[index]);
return 0;
}
|
Java
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
static int floorSearch(int arr[], int n, int x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.length;
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
System.out.print("Floor of " + x
+ " doesn't exist in array ");
else
System.out.print("Floor of " + x + " is "
+ arr[index]);
}
}
|
Python3
def floorSearch(arr, n, x):
if (x >= arr[n - 1]):
return n - 1
if (x < arr[0]):
return -1
for i in range(1, n):
if (arr[i] > x):
return (i - 1)
return -1
arr = [1, 2, 4, 6, 10, 12, 14]
n = len(arr)
x = 7
index = floorSearch(arr, n-1, x)
if (index == -1):
print("Floor of", x, "doesn't exist \
in array ", end="")
else:
print("Floor of", x, "is", arr[index])
|
C#
using System;
class GFG {
static int floorSearch(int[] arr, int n, int x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (int i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
static void Main()
{
int[] arr = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.Length;
int x = 7;
int index = floorSearch(arr, n - 1, x);
if (index == -1)
Console.WriteLine("Floor of " + x
+ " doesn't exist in array ");
else
Console.WriteLine("Floor of " + x + " is "
+ arr[index]);
}
}
|
PHP
<?php
function floorSearch($arr, $n, $x)
{
if ($x >= $arr[$n - 1])
return $n - 1;
if ($x < $arr[0])
return -1;
for ($i = 1; $i < $n; $i++)
if ($arr[$i] > $x)
return ($i - 1);
return -1;
}
$arr = array (1, 2, 4, 6, 10, 12, 14);
$n = sizeof($arr);
$x = 7;
$index = floorSearch($arr, $n - 1, $x);
if ($index == -1)
echo "Floor of ", $x,
"doesn't exist in array ";
else
echo "Floor of ", $x,
" is ", $arr[$index];
?>
|
Javascript
<script>
function floorSearch(arr, n, x)
{
if (x >= arr[n - 1])
return n - 1;
if (x < arr[0])
return -1;
for (let i = 1; i < n; i++)
if (arr[i] > x)
return (i - 1);
return -1;
}
let arr = [ 1, 2, 4, 6, 10, 12, 14 ];
let n = arr.length;
let x = 7;
let index = floorSearch(arr, n - 1, x);
if (index == -1)
document.write(
"Floor of " + x
+ " doesn't exist in array ");
else
document.write(
"Floor of " + x + " is "
+ arr[index]);
</script>
|
Time Complexity: O(N). To traverse an array only one loop is needed.
Auxiliary Space: O(1). No extra space is required
Floor in a Sorted Array using binary search:
To solve the problem follow the below idea:
There is a catch in the problem, the given array is sorted. The idea is to use Binary Search to find the floor of a number x in a sorted array by comparing it to the middle element and dividing the search space into half
Follow the given steps to solve the problem:
- The algorithm can be implemented recursively or through iteration, but the basic idea remains the same.
- There are some base cases to handle
- If there is no number greater than x then print the last element
- If the first number is greater than x then print -1
- create three variables low = 0, mid and high = n-1 and another variable to store the answer
- Run a loop or recurse until and unless low is less than or equal to high.
- check if the middle ( (low + high) /2) element is less than x, if yes then update the low, i.e low = mid + 1, and update the answer with the middle element. In this step we are reducing the search space to half.
- Else update the high , i.e high = mid – 1
- Print the answer
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int floorSearch(int arr[], int low, int high, int x)
{
if (low > high)
return -1;
if (x >= arr[high])
return high;
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return floorSearch(arr, low, mid - 1, x);
return floorSearch(arr, mid + 1, high, x);
}
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
cout << "Floor of " << x
<< " doesn't exist in array ";
else
cout << "Floor of " << x << " is " << arr[index];
return 0;
}
|
C
#include <stdio.h>
int floorSearch(int arr[], int low, int high, int x)
{
if (low > high)
return -1;
if (x >= arr[high])
return high;
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return floorSearch(arr, low, mid - 1, x);
return floorSearch(arr, mid + 1, high, x);
}
int main()
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
printf("Floor of %d doesn't exist in array ", x);
else
printf("Floor of %d is %d", x, arr[index]);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int floorSearch(int arr[], int low, int high,
int x)
{
if (low > high)
return -1;
if (x >= arr[high])
return high;
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return floorSearch(arr, low, mid - 1, x);
return floorSearch(arr, mid + 1, high, x);
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.length;
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
System.out.println(
"Floor of " + x
+ " doesn't exist in array ");
else
System.out.println("Floor of " + x + " is "
+ arr[index]);
}
}
|
Python3
def floorSearch(arr, low, high, x):
if (low > high):
return -1
if (x >= arr[high]):
return high
mid = int((low + high) / 2)
if (arr[mid] == x):
return mid
if (mid > 0 and arr[mid-1] <= x
and x < arr[mid]):
return mid - 1
if (x < arr[mid]):
return floorSearch(arr, low, mid-1, x)
return floorSearch(arr, mid + 1, high, x)
if __name__ == "__main__":
arr = [1, 2, 4, 6, 10, 12, 14]
n = len(arr)
x = 7
index = floorSearch(arr, 0, n-1, x)
if (index == -1):
print("Floor of", x, "doesn't exist\
in array ", end="")
else:
print("Floor of", x, "is", arr[index])
|
C#
using System;
class GFG {
static int floorSearch(int[] arr, int low, int high,
int x)
{
if (low > high)
return -1;
if (x >= arr[high])
return high;
int mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
if (mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return floorSearch(arr, low, mid - 1, x);
return floorSearch(arr, mid + 1, high, x);
}
public static void Main()
{
int[] arr = { 1, 2, 4, 6, 10, 12, 14 };
int n = arr.Length;
int x = 7;
int index = floorSearch(arr, 0, n - 1, x);
if (index == -1)
Console.Write("Floor of " + x
+ " doesn't exist in array ");
else
Console.Write("Floor of " + x + " is "
+ arr[index]);
}
}
|
Javascript
<script>
function floorSearch(
arr , low,
high , x)
{
if (low > high)
return -1;
if (x >= arr[high])
return high;
var mid = (low + high) / 2;
if (arr[mid] == x)
return mid;
if (
mid > 0 && arr[mid - 1] <= x && x < arr[mid])
return mid - 1;
if (x < arr[mid])
return floorSearch(
arr, low,
mid - 1, x);
return floorSearch(
arr, mid + 1, high,
x);
}
var arr = [ 1, 2, 4, 6, 10, 12, 14 ];
var n = arr.length;
var x = 7;
var index = floorSearch(
arr, 0, n - 1,
x);
if (index == -1)
document.write(
"Floor of " + x + " doesn't exist in array ");
else
document.write(
"Floor of " + x + " is " + arr[index]);
</script>
|
Time Complexity: O(log N). To run a binary search.
Auxiliary Space: O(1). As no extra space is required.
Please Login to comment...