- Floor: The largest element in the array that is less than or equal to the target.
- Ceil: The smallest element in the array that is greater than or equal to the target.
Problem Statement
Given a sorted array nums and an integer x. Find the floor and ceil of x in nums. The floor of x is the largest element in the array which is smaller than or equal to x. The ceiling of x is the smallest element in the array greater than or equal to x. If no floor or ceil exists, output -1.
Examples
Example 1:
Input: nums = [3, 4, 4, 7, 8, 10], x = 5
Output: 4, 7
Explanation: The floor value of 5 in the nums array is 4, and the ceiling value of 5 in the nums array is 7.Example 2:
Input: nums = [3, 4, 4, 7, 8, 10], x = 8
Output: 8, 8
Explanation: As the element 8 exists in the array, so it itself is the floor and ceil value.Example 3:
Input: nums = [3, 4, 4, 7, 8, 10], x = 11
Output: 10, -1
Explanation: As the element 11 is greater than every element of the nums array, so its floor value is the last element which is 10 and its ceil value is -1, as it itself does not exists and ther are no element which is greater than it.Different Approaches
1️⃣ Linear Search (Brute Force)
Floor Problem Using Linear Search
Algorithm:
- Traverse the array from left to right.
- Keep track of the largest element that is less than or equal to the target. If found, update the result.
- After traversing the entire array, return the result.
Dry Run:
For target = 5 and array = [1, 2, 4, 6, 8, 10]:
- Start with
res = -1. - Traverse the array:
- At index 0,
arr[0] = 1(≤ 5), so updateres = 1. - At index 1,
arr[1] = 2(≤ 5), so updateres = 2. - At index 2,
arr[2] = 4(≤ 5), so updateres = 4. - At index 3,
arr[3] = 6(> 5), no update. - Continue, but no updates as all other elements are greater than 5.
- At index 0,
- Final result:
res = 4.
Code:
#include <iostream>
#include <vector>
using namespace std;
int findFloorLinear(const vector<int>& arr, int target) {
int res = -1; // Initialize to handle cases when no floor is found
for (int i = 0; i < arr.size(); ++i) {
if (arr[i] <= target) {
res = arr[i]; // Update if arr[i] is less than or equal to the target
}
}
return res;
}
int main() {
vector<int> arr = {1, 2, 4, 6, 8, 10};
int target = 5;
int floorValue = findFloorLinear(arr, target);
if (floorValue != -1)
cout << "Floor of " << target << " is " << floorValue << endl;
else
cout << "Floor not found" << endl;
return 0;
}
Ceil Problem Using Linear Search
Algorithm:
- Traverse the array from left to right.
- Keep track of the smallest element that is greater than or equal to the target. If found, update the result.
- After traversing the entire array, return the result.
Dry Run:
For target = 5 and array = [1, 2, 4, 6, 8, 10]:
- Start with
res = -1. - Traverse the array:
- At index 0,
arr[0] = 1(< 5), no update. - At index 1,
arr[1] = 2(< 5), no update. - At index 2,
arr[2] = 4(< 5), no update. - At index 3,
arr[3] = 6(≥ 5), so updateres = 6. - Continue, but no updates as
6is the smallest value greater than 5.
- At index 0,
- Final result:
res = 6.
Code:
#include <iostream>
#include <vector>
using namespace std;
int findCeilLinear(const vector<int>& arr, int target) {
int res = -1; // Initialize to handle cases when no ceil is found
for (int i = 0; i < arr.size(); ++i) {
if (arr[i] >= target) {
if (res == -1 || arr[i] < res) {
res = arr[i]; // Update if arr[i] is closer to the target
}
}
}
return res;
}
int main() {
vector<int> arr = {1, 2, 4, 6, 8, 10};
int target = 5;
int ceilValue = findCeilLinear(arr, target);
if (ceilValue != -1)
cout << "Ceil of " << target << " is " << ceilValue << endl;
else
cout << "Ceil not found" << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
- Linear Search for Floor: We have to check every element, so the time complexity is
O(n). - Linear Search for Ceil: Similarly, we have to check every element, so the time complexity is
O(n).
- Linear Search for Floor: We have to check every element, so the time complexity is
- Space Complexity:
- Both approaches have a space complexity of
O(1)since no extra space is used apart from a few variables.
- Both approaches have a space complexity of
3️⃣ Binary Search (Optimal) Approach
Intuition:
For getting the floor value of x in nums, divide the array in two halves and compare the middle values with x. When x is less than or equal to the middle element, store the middle element as answer and will try to find a larger number that satisfies the same condition.
From the given statements, we can understand that the ceiling value of x, is basically the lower bound of x.
Approach:
Find floor
- Use two pointers, low and high initialized with the first and last indexes which will make our search space. Use an answer variable initialized with -1 to store the floor value.
- Calculate the middle element, and compare its value as described below :
- When the middle element is less than or equal to the given element, store it as a possible answer and eliminate the left half to look for a greater element in the right part of the array.
- In case the middle element is greater than the given element, eliminate the right half and reduce the search space to left half to look for a smaller element.
- Repeat these steps until the low pointer lesser than or equal to the high pointer.
- When the middle element is less than or equal to the given element, store it as a possible answer and eliminate the left half to look for a greater element in the right part of the array.
Dry Run:
+-----+-----+-----+-----+-----+-----+
nums = | 3 | 4 | 4 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
Target = 5First Iteration:
Target = 5
Left = 0
Right = 5
floorVal = -1
Mid = Left + (Right - Left) / 2
0 + (5 - 0) / 2 = 2
+-----+-----+-----+-----+-----+-----+
arr = | 3 | 4 | 4 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
Since arr[Mid] <= Target
4 <= 5
True
We would set the search space to the right side
floorVal = arr[Mid]
floorVal = 4
Left = Mid + 1Second Iteration:
Target = 5
Left = 3
Right = 5
floorVal = 4
Mid = Left + (Right - Left) / 2
3 + (5 - 3) / 2 = 3 + 2/2 = 4
+-----+-----+-----+-----+-----+-----+
arr = | 3 | 4 | 4 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
Left Mid Right
Since arr[Mid] <= Target
8 <= 5
false
We would set the search space to the left side, floorVal will remain unchanged
Right = Mid - 1
Right = 4 - 1 = 3Third Iteration:
Target = 5
Left = 3
Right = 3
floorVal = 4
Mid = Left + (Right - Left) / 2
3 + (3 - 3) / 2 = 3 + 0 = 3
+-----+-----+-----+-----+-----+-----+
arr = | 3 | 4 | 4 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
Left
Mid
Right
Since arr[Mid] <= Target
7 <= 5
false
We would set the search space to the left side, floorVal will remain unchanged
Right = Mid - 1
Right = 3 - 1 = 2Loop Termination:
floorVal = 4
+-----+-----+-----+-----+-----+-----+
arr = | 3 | 4 | 4 | 7 | 8 | 9 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
Right Left
Mid
Since Left <= Right
3 <= 2
false
Hence the loop will be terminated,
and return floorVal.Code:
#include <vector>
#include <iostream.h>
using namespace std;
// Helper function to find the floor of x
int findFloor(vector<int>& nums, int n, int x) {
int low = 0, high = n - 1;
int ans = -1;
// Perform binary search to find floor value
while (low <= high) {
int mid = low + (high - low) / 2;
/*Check if mid element lesser than
or equal to x, if it is update ans
and eliminate the left half */
if (nums[mid] <= x) {
// Go right
ans = nums[mid];
low = mid + 1;
} else {
// Go left
high = mid - 1;
}
}
return ans;
}
int main() {
vector<int> nums = {3, 4, 4, 7, 8, 9};
int target = 5;
int floor = findFloor(nums, nums.size(), target);
}Complexity Analysis:
- Time Complexity:
O(logN), whereNis the size of the given array. We are using the Binary Search algorithm, which divides the search space in half each time, resulting in a logarithmic time complexity. - Space Complexity:
O(1), as we are not using any extra space to solve this problem.
Find Ceil
- For calculating the ceil value, follow a similar approach, but compare the values depending upon the below points:
- In this case, store the middle element as a possible answer when the middle elements value is greater than or equal to the given element. Eliminate the right half to look for a smaller element in the left half which satisfies the same condition.
- When the middle element is smaller than the given element, eliminate the left half to search for a larger element in the right half of the given array.
Algorithm
- Set
left = 0andright = n - 1. - Initialize
res = -1to store the potential ceil element. - While
left <= right:- Calculate
mid = left + (right - left) / 2. - If
arr[mid]is greater than or equal to the target, updateres = arr[mid](as it's a potential ceil) and moverighttomid - 1. - Otherwise, move
lefttomid + 1.
- Calculate
- Return
res, which will contain the ceil of the target.
Code:
#include <vector>
#include <iostream.h>
using namespace std;
// Helper function to find the ceil of x
int findCeil(vector<int>& nums, int n, int x) {
int low = 0, high = n - 1;
int ans = -1;
// Perform binary search to find ceil value
while (low <= high) {
int mid = (low + high) / 2;
/*Check if mid element greater than
or equal to x, if it is update ans
and eliminate the left half */
if (nums[mid] >= x) {
// Go left
ans = nums[mid];
high = mid - 1;
} else {
// Go right
low = mid + 1;
}
}
return ans;
}
int main() {
vector<int> nums = {3, 4, 4, 7, 8, 9};
int target = 5;
int floor = findCeil(nums, nums.size(), target);
}Complexity Analysis:
- Time Complexity:
O(logN), whereNis the size of the given array. We are using the Binary Search algorithm, which divides the search space in half each time, resulting in a logarithmic time complexity. - Space Complexity:
O(1), as we are not using any extra space to solve this problem.
Combined Code:
class Solution {
public:
// Function to find the floor and ceiling values of 'x' in a sorted array 'nums'
vector<int> getFloorAndCeil(vector<int> nums, int x) {
int left = 0; // Initialize left pointer to the start of the array
int right = nums.size() - 1; // Initialize right pointer to the end of the array
int floor = -1; // Default value for floor if no floor is found
// Binary search to find the floor of 'x'
while(left <= right) {
int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow
if(nums[mid] == x) { // If mid element equals 'x'
floor = nums[mid]; // Set floor to x
// Optional: break here as both floor and ceil are 'x'
left = mid + 1; // Move right to check for duplicate elements of 'x'
} else if(nums[mid] > x) { // If mid element is greater than 'x'
right = mid - 1; // Move to the left half
} else { // If mid element is less than 'x'
floor = nums[mid]; // Update floor to current mid element
left = mid + 1; // Move to the right half
}
}
// Reset left and right pointers to search for the ceiling of 'x'
left = 0;
right = nums.size() - 1;
int ceil = -1; // Default value for ceil if no ceil is found
// Binary search to find the ceiling of 'x'
while(left <= right) {
int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow
if(nums[mid] == x) { // If mid element equals 'x'
ceil = nums[mid]; // Set ceil to x
// Optional: break here as both floor and ceil are 'x'
right = mid - 1; // Move left to check for duplicate elements of 'x'
} else if (nums[mid] > x) { // If mid element is greater than 'x'
ceil = nums[mid]; // Update ceil to current mid element
right = mid - 1; // Move to the left half
} else { // If mid element is less than 'x'
left = mid + 1; // Move to the right half
}
}
return {floor, ceil}; // Return the values of floor and ceil
}
};