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



This article is attributed to GeeksforGeeks.org

tags:

Divide and Conquer Searching Amazon Binary Search Amazon Searching Divide and Conquer Binary Search
Prev Next
More topics on Searching Algorithms

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter

Top Followed books

Searching Algorith... Find the first repeating eleme...
Searching Algorith... Minimum time required to produ...
Searching Algorith... Find the largest pair sum in a...
Searching Algorith... Print all possible sums of con...
Searching Algorith... K’th largest element in a st...
Searching Algorith... Find the element before which ...