排序数组中的楼层

Question

我有一个大小为 n 且没有重复项的排序数组 arr[]，并且给定了一个值 x。 x 的下限定义为 arr[] 中最大的元素 K，使得 K 小于或等于 x。找到 K（基于 0 的索引）.

的索引

输入：

n = 7
x = 0
arr[] = {1,2,8,10,11,12,19}

输出：

我必须在 O(logn) 中解决它。我下面的代码通过了测试用例，但显示超出了时间限制。这段代码有什么问题？

static int findFloor(long arr[], int n, long x) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else if (arr[mid] < x) {
            low = mid + 1;
        }
    }
    return -1;
}

Answer 1

您的程序将因 arr[mid] == x 案例无限停滞，因为您尚未处理此案例。另外，我也没有看到这个程序在其他情况下也能正常工作。

例如，如果我给 x=7，这将 return 索引 2，这是错误的。正确的索引应该是 1，因为 x=7 大于 arr[1] == 2 且小于 arr[2] == 8。

此外，如果我给出的输入大于数组中的最后一个元素，您的代码将会中断，例如您的示例中的 x=50。你会得到一个 ArrayIndexOutOfBoundException，因为你的 low 会增加并使 mid 索引超出范围。

我已经纠正了上述情况，固定功能如下：

static int findFloor(long[] arr, int n, long x) {
    if (x >= arr[arr.length - 1]) {
        return arr.length - 1;
    }
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            if (arr[mid] == x || (mid != 0 && arr[mid + 1] > x)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

希望你得到答案。

排序数组中的楼层

Floor in a Sorted Array

java

binary-search