Floor in a Sorted Array

Given a sorted array and a value x, the floor of x is the largest element in array smaller than or equal to x. Write efficient functions to find floor of x.

Examples:

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output : 2
2 is the largest element in arr[] smaller than 5.

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20
Output : 19
19 is the largest element in arr[] smaller than 20.

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0
Output : -1
Since floor doesn't exist, output is -1.

Method 1 (Simple)
A simple solution is linearly traverse input sorted array and search for the first element greater than x. The element just before the found element is floor of x.

C++

// C/C++ program to find floor of a given number  
// in a sorted array  
#include<stdio.h>  
  
/* An inefficient function to get index of floor  
of x in arr[0..n-1] */
int floorSearch(int arr[], int n, int x)  
{  
    // If last element is smaller than x  
    if (x >= arr[n-1])  
        return n-1;  
  
    // If first element is greater than x  
    if (x < arr[0])  
        return -1;  
  
    // Linearly search for the first element  
    // greater than x  
    for (int i=1; i<n; i++)  
    if (arr[i] > x)  
        return (i-1);  
  
    return -1;  
}  
  
/* Driver program to check above functions */
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;  
}  

/div>

Java

// Java program to find floor of a given number  
// in a sorted array  
import java.io.*; 
import java.util.*; 
import java.lang.*; 
  
class GFG 
{ 
  
/* An inefficient function to get index of floor  
of x in arr[0..n-1] */
static int floorSearch(int arr[], int n, int x)  
{  
    // If last element is smaller than x  
    if (x >= arr[n-1])  
        return n-1;  
  
    // If first element is greater than x  
    if (x < arr[0])  
        return -1;  
  
    // Linearly search for the first element  
    // greater than x  
    for (int i=1; i<n; i++)  
    if (arr[i] > x)  
        return (i-1);  
  
    return -1;  
}  
  
// Driver Code 
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]);  
}  
}  
  
// This code is contributed  
// by Akanksha Rai(Abby_akku) 

Python3

# Python3 program to find floor of a  
# given number in a sorted array  
  
# Function to get index of floor  
# of x in arr[low..high]  
def floorSearch(arr, low, high, x):  
  
    # If low and high cross each other  
    if (low > high):  
        return -1
  
    # If last element is smaller than x  
    if (x >= arr[high]):  
        return high  
  
    # Find the middle point  
    mid = int((low + high) / 2)  
  
    # If middle point is floor.  
    if (arr[mid] == x):  
        return mid  
  
    # If x lies between mid-1 and mid  
    if (mid > 0 and arr[mid-1] <= x  
                and x < arr[mid]):  
        return mid - 1
  
    # If x is smaller than mid,  
    # floor must be in left half.  
    if (x < arr[mid]):  
        return floorSearch(arr, low, mid-1, x)  
  
    # If mid-1 is not floor and x is greater than  
    # arr[mid],  
    return floorSearch(arr, mid+1, high, x)  
  
  
# Driver Code  
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])  
  
# This code is contributed by Smitha Dinesh Semwal.  

PHP

<?php 
// PHP program to find floor of  
// a given number in a sorted array  
  
/* An inefficient function  
   to get index of floor  
   of x in arr[0..n-1] */
  
function floorSearch($arr, $n, $x)  
{  
    // If last element is smaller 
    // than x  
    if ($x >= $arr[$n - 1])  
        return $n - 1;  
  
    // If first element is greater 
    // than x  
    if ($x < $arr[0])  
        return -1;  
  
    // Linearly search for the  
    // first element greater than x  
    for ($i = 1; $i < $n; $i++)  
    if ($arr[$i] > $x)  
        return ($i - 1);  
  
    return -1;  
}  
  
// Driver Code 
$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];  
      
// This code is contributed by ajit 
?> 

Output:

Floor of 7 is 6.

Time Complexity : O(n)

Method 2 (Efficient)
The idea is to use Binary Search.

C++

// A C/C++ program to find floor of a given number 
// in a sorted array 
#include<stdio.h> 
  
/* Function to get index of floor of x in 
   arr[low..high] */
int floorSearch(int arr[], int low, int high, int x) 
{ 
    // If low and high cross each other 
    if (low > high) 
        return -1; 
  
    // If last element is smaller than x 
    if (x >= arr[high]) 
        return high; 
  
    // Find the middle point 
    int mid = (low+high)/2; 
  
    // If middle point is floor. 
    if (arr[mid] == x) 
        return mid; 
  
    // If x lies between mid-1 and mid 
    if (mid > 0 && arr[mid-1] <= x && x < arr[mid]) 
        return mid-1; 
  
    // If x is smaller than mid, floor must be in 
    // left half. 
    if (x < arr[mid]) 
        return floorSearch(arr, low, mid-1, x); 
  
    // If mid-1 is not floor and x is greater than 
    // arr[mid], 
    return floorSearch(arr, mid+1, high, x); 
} 
  
/* Driver program to check above functions */
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

// Java program to find floor of 
// a given number in a sorted array 
import java.io.*; 
  
class GFG { 
      
    /* Function to get index of floor of x in 
    arr[low..high] */
    static int floorSearch(int arr[], int low,  
                            int high, int x) 
    { 
        // If low and high cross each other 
        if (low > high) 
            return -1; 
  
        // If last element is smaller than x 
        if (x >= arr[high]) 
            return high; 
  
        // Find the middle point 
        int mid = (low+high)/2; 
  
        // If middle point is floor. 
        if (arr[mid] == x) 
            return mid; 
  
        // If x lies between mid-1 and mid 
        if (mid > 0 && arr[mid-1] <= x && x < 
                                    arr[mid]) 
            return mid-1; 
  
        // If x is smaller than mid, floor 
        // must be in left half. 
        if (x < arr[mid]) 
            return floorSearch(arr, low,  
                               mid - 1, x); 
  
        // If mid-1 is not floor and x is 
        // greater than arr[mid], 
        return floorSearch(arr, mid + 1, high, 
                                         x); 
    } 
  
    /* Driver program to check above functions */
    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 + 
                     " dosen't exist in array "); 
        else
            System.out.println("Floor of " + x + 
                            " is " + arr[index]); 
    } 
} 
// This code is contributed by Prerna Saini 

Python3

# Python3 program to find floor of a   
# given number in a sorted array 
  
# Function to get index of floor  
# of x in arr[low..high]  
def floorSearch(arr, low, high, x): 
  
    # If low and high cross each other 
    if (low > high): 
        return -1
  
    # If last element is smaller than x 
    if (x >= arr[high]): 
        return high 
  
    # Find the middle point 
    mid = int((low + high) / 2) 
  
    # If middle point is floor. 
    if (arr[mid] == x): 
        return mid 
  
    # If x lies between mid-1 and mid 
    if (mid > 0 and arr[mid-1] <= x  
                and x < arr[mid]): 
        return mid - 1
  
    # If x is smaller than mid,   
    # floor must be in left half. 
    if (x < arr[mid]): 
        return floorSearch(arr, low, mid-1, x) 
  
    # If mid-1 is not floor and x is greater than 
    # arr[mid], 
    return floorSearch(arr, mid+1, high, x) 
  
  
# Driver Code 
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]) 
  
# This code is contributed by Smitha Dinesh Semwal. 

C#

// C# program to find floor of 
// a given number in a sorted array 
using System; 
   
class GFG { 
       
    /* Function to get index of floor of x in 
    arr[low..high] */
    static int floorSearch(int []arr, int low,  
                              int high, int x) 
    { 
  
        // If low and high cross each other 
        if (low > high) 
            return -1; 
   
        // If last element is smaller than x 
        if (x >= arr[high]) 
            return high; 
   
        // Find the middle point 
        int mid = (low + high) / 2; 
   
        // If middle point is floor. 
        if (arr[mid] == x) 
            return mid; 
   
        // If x lies between mid-1 and mid 
        if (mid > 0 && arr[mid-1] <= x && x < 
                                    arr[mid]) 
            return mid - 1; 
   
        // If x is smaller than mid, floor 
        // must be in left half. 
        if (x < arr[mid]) 
            return floorSearch(arr, low,  
                               mid - 1, x); 
   
        // If mid-1 is not floor and x is 
        // greater than arr[mid], 
        return floorSearch(arr, mid + 1, high, 
                                         x); 
    } 
   
    /* Driver program to check above functions */
    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 + 
                     " dosen't exist in array "); 
        else
            Console.Write("Floor of " + x + 
                            " is " + arr[index]); 
    } 
} 
  
// This code is contributed by nitin mittal. 

Output:

Floor of 7 is 6.

Time Complexity : O(Log n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

C++

Java

Python3

PHP

C++

Java

Python3

C#

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books