Tutorialspoint.dev

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; 

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] <=
                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] <=
                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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter