我有一个排序数组 arr[]
大小 n
没有重复项,并且给定了一个值 x
. 地板 x
定义为中的最大元素k arr[]
使得k小于或等于 x
. 查找k的索引(基于0的索引)。
输入:
n = 7
x = 0
arr[] = {1,2,8,10,11,12,19}
输出:
1
我必须在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;
}
1条答案
按热度按时间h43kikqp1#
在这种情况下,您的程序将陷入无限状态
arr[mid] == x
因为你没有处理过这个案子。另外,我不认为这个程序在其他情况下也能正常工作。例如,如果我给
x=7
,这将返回索引2
,这是错误的。正确的索引应该是1
作为x=7
比arr[1] == 2
不到arr[2] == 8
.另外,如果我输入的值大于数组中的最后一个元素,比如
x=50
在你的例子中。你会得到一份工作的ArrayIndexOutOfBoundException
作为你的low
将增加并使mid
索引越界。我已经纠正了上述情况,修复函数如下所示:
希望你得到你的答案。