Given a sorted array of distinct integers and a target value, find the index of the floor of the target in the array.
The floor of a target is defined as the largest element in the array that is smaller than or equal to the target. If no such element exists (i.e., all elements are greater than the target), return -1.
Example 1
Input: arr = [1, 3, 5, 7, 9], target = 6
Output: 2
Explanation: The largest element smaller than or equal to 6 is 5, and 5 is present at index 2.
Example 2
Input: arr = [2, 4, 6, 8, 10], target = 1
Output: -1
Explanation: Every element is greater than 1, so the floor does not exist.
Brute Force Approach
The simplest idea is to move from left to right and keep track of the latest value that is still less than or equal to the target.
Because the array is sorted, once a value becomes greater than the target, no later value can be a valid floor. That means the search can stop immediately.
So the answer is simply the last valid index seen before the array crosses the target.
Algorithm
Start with a variable
answer = -1. This is useful because if no element is smaller than or equal to the target,-1should remain the final result.Traverse the array from left to right because the values are already in sorted order, and every next element is greater than the previous one.
For each element, check whether it is less than or equal to the target. If it is, update
answerto that index because it is a valid floor candidate seen so far.Keep moving forward while the values stay less than or equal to the target, because a later valid element would always be a better floor than an earlier one.
If the current element becomes greater than the target, stop immediately. This is done because every element after it will also be greater, so no better floor can appear later.
Return
answerafter the loop ends, because it stores the index of the largest valid value found during the scan.
Key Points
If the target is greater than all elements, the last index becomes the answer.
Dry Run
Find Floor Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of the largest element that is smaller than or equal to the target. */ int findFloor(vector<int>& arr, int target) { // Store the best floor index found so far. int answer = -1; // Check each value from left to right. for (int i = 0; i < (int)arr.size(); i++) { // This value is a valid floor candidate, so remember its index. if (arr[i] <= target) { answer = i; } else { // Once the value becomes too large, no later value can help. break; } } return answer; }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 7, 9}; int target = 6; Solution obj; cout << obj.findFloor(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because in the worst case the whole array may need to be scanned.
Space Complexity: O(1), because only a few variables are used.
Optimal Approach
The important observation is this: if arr[mid] is less than or equal to the target, then mid is a valid floor candidate.
But that may not be the best one, because there could still be a larger valid value on the right side. So that index should be remembered, and the search should continue to the right.
If arr[mid] is greater than the target, then mid cannot be the floor, and the search must move to the left side.
This pattern keeps narrowing the range while always preserving the best valid answer found so far.
Algorithm
Start with two pointers:
low = 0andhigh = n - 1. These pointers represent the current search range where the floor might still exist.Keep a variable
answer = -1to store the best floor index found so far. This default value is important because it already matches the required output when no floor exists.Find the middle index of the current range. The middle value helps decide which half of the array can still contain the correct answer.
If
arr[mid]is less than or equal to the target, thenmidis a valid floor candidate. Store this index inanswerbecause it may be the answer.After finding a valid candidate, move
lowtomid + 1. This is done to search on the right side for a larger value that is still less than or equal to the target.If
arr[mid]is greater than the target, movehightomid - 1because the floor must be smaller, so only the left half can still help.Repeat this process until
lowbecomes greater thanhigh. At that point, the search range becomes empty and no unchecked candidate remains.Return
answer, because it stores the index of the largest element that stayed within the target limit during the search.
Dry Run
Find Floor Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the index of the largest element that is smaller than or equal to the target. */ int findFloor(vector<int>& arr, int target) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)arr.size() - 1; // Store the best floor index found so far. int answer = -1; // Keep searching while a valid range still exists. while (low <= high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // This value can be a floor, so store it and try to find a larger one. if (arr[mid] <= target) { answer = mid; low = mid + 1; } else { // This value is too large, so move to the left half. high = mid - 1; } } return answer; }};// Driver code startsint main() { vector<int> arr = {1, 3, 5, 7, 9}; int target = 6; Solution obj; cout << obj.findFloor(arr, target) << endl; return 0;}Complexity Analysis
Time Complexity: O(log N), N is the length of array, because the search range becomes half in each step.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
Return -1, because no valid floor exists in that case.
Be the first to add a comment.