java - 尝试在 T 数组中使用二分搜索方法递归查找数字时出现 StackOverflowError

Question

嘿，我正在使用二分搜索方法在数组中查找数字，但在查找中间数字以外的数字时，出现 StackOverflow 错误。

这是我的代码:

public static  <T extends Comparable< ? super T>>
    int find(T [] a, T x, int low, int high){
    if(low>high)
        throw new IllegalArgumentException();
    int tmp = (high-low)/2;

    if(a[tmp].compareTo(x)==0)
        return tmp;
    else if(a[tmp].compareTo(x)>0)
        find(a,x,tmp,high);
    else if(a[tmp].compareTo(x)<0)
        find(a,x,low,tmp);
    return -1;
}

此外，如果我尝试在 tmp 下查找数字，它会返回 -1。我觉得我错过了一些东西，但又不知道是什么。提前致谢!

Answer 1

这就是问题:

if(a[tmp].compareTo(x)>0)
    find(a,x,tmp,high);
else if(a[tmp].compareTo(x)<0)
    find(a,x,low,tmp);

您应该在第一种情况下使用tmp + 1，在第二种情况下使用tmp - 1。否则，如果您(例如)low = 0，high = 1，那么您可能会永远使用相同的参数进行调用； tmp 最终将为 0，如果 x 大于 a[0]，您只需调用 find(a, x, 0, 1) 再次。

无论如何，这是我的直觉。您确实应该记录所使用的低/高值所发生的情况 - 我相信您会在发出声音之前看到某种重复。

编辑:您也以错误的方式进行比较。如果 a[tmp] 小于 x，a[tmp].compareTo(x) 将返回一个小于 0 的值 - 即你应该在数组中稍后查看，而不是更早。

编辑:目前您的“exit with -1”代码已损坏 - 如果 a[tmp].compareTo(x) 返回非零值，则您只会返回 -1既不高于零也不低于零。我挑战你找到这样一个整数:)(如果compareTo不稳定的话它也会这样做，但这是一个单独的问题......)

一个选项是检测是否high == low - 此时，如果没有达到正确的值，则可以返回 -1:

int comparison = a[tmp].compareTo(x); // Let's just compare once...
if (comparison == 0) {
   return tmp;
}
// This was our last chance!
if (high == low) {
   return -1;
}
// If a[tmp] was lower than x, look later in the array. If it was higher than
// x, look earlier in the array.
return comparison < 0 ? find(a, x, tmp + 1, high) : find(a, x, low, tmp - 1);