降序数组中数值的Ceiling与Floor求解问题（Java）

问题描述 #

针对降序数组{10, 9, 8, 7, 4, 3, 2, 1}，查找目标值6的Ceiling（大于等于目标值的最小元素，对应索引3，值为7）和Floor（小于等于目标值的最大元素，对应索引4，值为4），但现有代码运行后，ceilingOfNumber返回4，floorOfNumber返回3，结果与预期完全相反。

问题原因 #

代码中循环结束后的返回逻辑直接沿用了升序数组的规则，没有根据数组的排序方向做调整：

• 升序数组中，Ceiling对应循环结束后的start，Floor对应end；
• 降序数组中，这个逻辑完全颠倒，Ceiling应对应end，Floor应对应start。

原代码未区分排序方向直接返回固定值，导致降序场景下结果错误。

修复后的代码 #

public class BinarySearchAlgorithm {
    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 4, 3, 2, 1};
        int target = 6;
        System.out.println(ceilingOfNumber(arr, target)); // 输出3
        System.out.println(floorOfNumber(arr, target));   // 输出4
    }
    
    static int ceilingOfNumber(int[] arr, int target) {
        int start = 0;
        int end = arr.length -1;
        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid]) {
                return mid;
            }

            if (isAscending) {
                if (target > arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid -1;
                }
            } else {
                if (target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        // 根据排序方向返回对应值
        return isAscending ? start : end;
    }

    static int floorOfNumber(int[] arr, int target) {
        int start = 0;
        int end = arr.length -1;
        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid]) {
                return mid;
            }

            if (isAscending) {
                if (target > arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid -1;
                }
            } else {
                if (target > arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        // 根据排序方向返回对应值
        return isAscending ? end : start;
    }
}

修复逻辑说明 #

• Ceiling方法：循环结束后，升序数组返回start（指向第一个大于等于目标值的元素），降序数组返回end（指向最后一个大于等于目标值的元素，即降序中最小的符合条件元素）；
• Floor方法：循环结束后，升序数组返回end（指向最后一个小于等于目标值的元素），降序数组返回start（指向第一个小于等于目标值的元素，即降序中最大的符合条件元素）。

内容的提问来源于stack exchange，提问作者Rushan Shaikh