Mostafa Shariare

Posted on

# ðŸ”ŽFinding Ceiling and Floor using Binary Search in Java (Handling Both Ascending and Descending Arrays)

#### 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 the `target` is greater than the middle element. If the array is sorted in descending order, we adjust the `end` pointer instead.

• Floor: The logic for the floor is similar but inverted. In ascending order, we adjust the `end` pointer when `target` is smaller than the middle element, and in descending order, we adjust the `start` 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

1. 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` and `floor`, are implemented. Both use binary search but with slightly different logic based on whether the array is ascending or descending.
2. Binary Search Logic:

• For the ceiling:
• If the array is ascending and the target is smaller than the middle element, we move `end` to `mid - 1`. If the target is larger, we move `start` to `mid + 1`.
• In the case of a descending array, this logic is reversed.
• For the floor:
• The same logic applies, but the roles of `start` and `end` are swapped.
3. Edge Cases:

• If the `target` is not found, the ceiling function returns `arr[start]` (the smallest element greater than or equal to the target) and the floor function returns `arr[end]` (the largest element less than or equal to the target).
4. 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! ðŸš€