Given a sorted array and a value x, find the element of the floor of x. The floor of x is the largest element in the array smaller than or equal to x.
Examples:
Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 5
Output: 1
Explanation: Largest number less than or equal to 5 is 2, whose index is 1
Input: arr[] = [1, 2, 8, 10, 10, 12, 19], x = 20
Output: 6
Explanation: Largest number less than or equal to 20 is 19, whose index is 6
Input : arr[] = [1, 2, 8, 10, 10, 12, 19], x = 0
Output : -1
Explanation: Since floor doesn't exist, output is -1.
[Naive Method] – Using Linear Search – O(n) Time and O(1) Space
Traverse the array from start to end. If the first element is greater than x, print "Floor of x doesn't exist." Otherwise, when encountering an element greater than x, print the previous element and exit. If no such element is found, print the last element as the floor of x.
C++ #include <bits/stdc++.h> using namespace std; /* An function to get index of floor of x in arr */ int findFloor(vector<int> &arr, int x) { int n = arr.size(); // 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 int ans = -1; for (int i = 0; i < n; i++) { if (arr[i] > x) { return (i - 1); } } return ans; } /* Driver program to check above functions */ int main() { vector<int> arr = {1, 2, 4, 6, 10, 12, 14}; int x = 7; int index = findFloor(arr, x); cout << index; return 0; } import java.util.Arrays; class GfG { static int findFloor(int arr[], int x) { int n = arr.length; // 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 // greater than x int ans = -1; for (int i = 0; i < n; i++) { if (arr[i] > x) { return (i-1); } } return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; int index = findFloor(arr, x); System.out.print(index); } } def findFloor(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 ans = -1 for i in range(0, n): if (arr[i] > x): return (i-1) return ans # Driver Code arr = [1, 2, 4, 6, 10, 12, 14] n = len(arr) x = 7 index = findFloor(arr, n - 1, x) print(index)
// C# program to find floor of a given number // in a sorted array using System; class GfG { static int findFloor(int[] arr, int x) { // If last element is smaller than x int n = arr.Length; 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 int ans = -1; for (int i = 0; i < n; i++) if (arr[i] > x) { return (i-1); } return ans; } // Driver Code static void Main() { int[] arr = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; int index = findFloor(arr, x); Console.WriteLine(index); } } // This code is contributed // by mits function findFloor(arr, x) { let n = arr.length; 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 let ans = -1; for (let i = 0; i < n; i++) if (arr[i] > x) { return (i-1); } return ans; } // Driver Code let arr = [ 1, 2, 4, 6, 10, 12, 14 ]; let n = arr.length; let x = 7; let index = findFloor(arr, x); console.log(index); [Expected Approach] – Using Binary Search – O(Log n) Time and O(1) Space
Find the midpoint. If arr[mid] equals x, return mid. If arr[mid] is greater than x, search the left half. Otherwise, store arr[mid] as a potential floor and continue searching the right half for a larger but valid floor value.
C++ #include <bits/stdc++.h> using namespace std; int findFloor(vector<int> &arr, int x) { // Your code here int ans = -1; int low = 0; int high = arr.size() - 1; while (low <= high) { int mid = (low + high) / 2; if (arr[mid] > x) { high = mid - 1; } else if (arr[mid] <= x) { ans = mid; low = mid + 1; } } return ans; } int main() { vector<int> arr = {1, 2, 4, 6, 10, 10, 12, 14}; int x = 11; // Function call int index = findFloor(arr, x); cout << index; return 0; } import java.io.*; class GfG { static int findFloor(int arr[], int x) { int n = arr.length; int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] <= x) { result = mid; low = mid + 1; } else { high = mid - 1; // Move left } } return result; } public static void main(String[] args) { int arr[] = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; // Function call int index = findFloor(arr, x); System.out.println(index); } } # Function to find the floor of x using binary search (Iterative) def findFloor(arr, x): n = len(arr) low, high = 0, n - 1 result = -1 while low <= high: mid = (low + high) // 2 if arr[mid] <= x: result = mid # Possible floor low = mid + 1 # Move right else: high = mid - 1 # Move left return result if __name__ == "__main__": arr = [1, 2, 4, 6, 10, 12, 14] x = 7 # Function call index = findFloor(arr, x) print(index)
using System; class GfG { static int findFloor(int[] arr, int x) { int n = arr.Length; int low = 0, high = n - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] <= x) { result = mid; low = mid + 1; } else { high = mid - 1; } } return result; } public static void Main() { int[] arr = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; // Function call int index = findFloor(arr, x); Console.Write(index); } } function findFloor(arr, x) { let n = arr.length; let low = 0, high = n - 1; let result = -1; while (low <= high) { let mid = Math.floor((low + high) / 2); if (arr[mid] <= x) { result = mid; // Possible floor low = mid + 1; // Move right } else { high = mid - 1; // Move left } } return result; } // Test the function let arr = [ 1, 2, 4, 6, 10, 12, 14 ]; let x = 7; let index = findFloor(arr, x); console.log(index); [Another Approach] Using Library Methods - O(Log n) Time and O(1) Space
We can use the following library methods in different languages.
The upper_bound() method in C++, Arrays.binarySearch() in Java and C#, bisect_right() in Python and findIndex
C++ #include <bits/stdc++.h> using namespace std; int findFloor(vector<int>& arr, int x) { auto itr = upper_bound(arr.begin(), arr.end(), x); if (itr == arr.begin()) return -1; itr--; return itr - arr.begin(); } int main() { vector<int> arr = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; int index = findFloor(arr, x); cout<<index; return 0; } import java.util.Arrays; class GfG { static int findFloor(int[] arr, int x) { int idx = Arrays.binarySearch(arr, x); // If element not found, get insertion position if (idx < 0) { idx = Math.abs(idx) - 2; // Move to the previous index } return (idx >= 0) ? idx : -1; // Return -1 if no floor exists } public static void main(String[] args) { int arr[] = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; int floorindex = findFloor(arr, x); System.out.println(floorindex); } } import bisect def findFloor(arr, x): idx = bisect.bisect_right(arr, x) - 1 return idx if idx >= 0 else -1 arr = [1, 2, 4, 6, 10, 12, 14] x = 7 index = findFloor(arr, x) print(index)
using System; class GfG { static int findFloor(int[] arr, int x) { int idx = Array.BinarySearch(arr, x); // If x is found in the array, return the index directly if (idx >= 0) { return idx; } // If x is not found, find the largest element smaller than x idx = ~idx - 1; // ~idx = -(insertion_point) - 1 // If idx is valid, return it; otherwise, return -1 (no floor exists) return (idx >= 0) ? idx : -1; } public static void Main() { int[] arr = { 1, 2, 4, 6, 10, 12, 14 }; int x = 7; int index = findFloor(arr, x); Console.WriteLine(index); } } function findFloor(arr, x) { // Use findLastIndex() to find the last element that is // <= x let idx = arr.slice().reverse().findIndex(val => val <= x); // Adjust index since findLastIndex() is used on a // reversed array if (idx !== -1) { idx = arr.length - 1 - idx; } return idx; } let arr = [ 1, 2, 4, 6, 10, 12, 14 ]; const x = 7; let index = findFloor(arr, x); // Checking if idx is valid console.log(index) Related Articles:
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile