Problem Statement
Given a sorted array arr
and a target value target
, implement two functions—one to find the ceiling and another to find the floor of the target in the array. The ceiling of a target is the smallest element that is greater than or equal to the target, and the floor is the largest element that is less than or equal to the target.
Additionally, the array can be either in ascending or descending order.
For example:
-
Input:
arr = {2, 3, 5, 9, 14, 17, 18}
,target = 15
-
Output:
Floor = 14
,Ceiling = 17
For descending order:
-
Input:
arr = {18, 17, 14, 9, 5, 3, 2}
,target = 15
-
Output:
Floor = 14
,Ceiling = 17
Approach
We'll use binary search to find the ceiling and floor of the target efficiently. The core idea is to identify whether the array is sorted in ascending or descending order and adjust our logic accordingly.
Ceiling: If the array is sorted in ascending order, we adjust the
start
pointer when thetarget
is greater than the middle element. If the array is sorted in descending order, we adjust theend
pointer instead.Floor: The logic for the floor is similar but inverted. In ascending order, we adjust the
end
pointer whentarget
is smaller than the middle element, and in descending order, we adjust thestart
pointer.
Code Implementation
Let's implement both functions, one for finding the ceiling and one for finding the floor. We will determine whether the array is in ascending or descending order and apply binary search accordingly.
public class CeilingAndFloor {
// Function to find the ceiling of the target
public static int ceiling(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
boolean isAscending = arr[start] < arr[end]; // Determine if the array is ascending
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return arr[mid]; // Target is found, return it as the ceiling
}
if (isAscending) {
if (target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else { // If the array is in descending order
if (target > arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
// If the loop ends, start will point to the smallest number greater than target (the ceiling)
return arr[start];
}
// Function to find the floor of the target
public static int floor(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
boolean isAscending = arr[start] < arr[end]; // Determine if the array is ascending
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return arr[mid]; // Target is found, return it as the floor
}
if (isAscending) {
if (target < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else { // If the array is in descending order
if (target > arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
// If the loop ends, end will point to the largest number less than target (the floor)
return arr[end];
}
public static void main(String[] args) {
int[] arr = {2, 3, 5, 9, 14, 17, 18}; // Ascending order array
int target = 15;
System.out.println("Ceiling: " + ceiling(arr, target)); // Output: 17
System.out.println("Floor: " + floor(arr, target)); // Output: 14
int[] arrDesc = {18, 17, 14, 9, 5, 3, 2}; // Descending order array
System.out.println("Ceiling: " + ceiling(arrDesc, target)); // Output: 17
System.out.println("Floor: " + floor(arrDesc, target)); // Output: 14
}
}
Explanation
-
Initial Setup:
- We determine whether the array is in ascending or descending order by comparing the first and last elements of the array (
arr[start] < arr[end]
). - Two functions,
ceiling
andfloor
, are implemented. Both use binary search but with slightly different logic based on whether the array is ascending or descending.
- We determine whether the array is in ascending or descending order by comparing the first and last elements of the array (
-
Binary Search Logic:
- For the ceiling:
- If the array is ascending and the target is smaller than the middle element, we move
end
tomid - 1
. If the target is larger, we movestart
tomid + 1
. - In the case of a descending array, this logic is reversed.
- If the array is ascending and the target is smaller than the middle element, we move
- For the floor:
- The same logic applies, but the roles of
start
andend
are swapped.
- The same logic applies, but the roles of
- For the ceiling:
-
Edge Cases:
- If the
target
is not found, the ceiling function returnsarr[start]
(the smallest element greater than or equal to the target) and the floor function returnsarr[end]
(the largest element less than or equal to the target).
- If the
Time Complexity: The binary search approach ensures that the solution runs in
O(log n)
time, making it efficient for large arrays.
Conclusion
By incorporating both ascending and descending order handling in our binary search approach, we've created a versatile solution for finding the ceiling and floor of a target value in any sorted array. This approach is not only efficient but also adaptable to different types of input arrays.
Understanding and mastering binary search problems like these is crucial for becoming proficient in coding interviews and competitive programming. Try experimenting with different inputs and arrays to solidify your understanding.
Happy coding! 🚀
Top comments (0)