递归二进制搜索和 return 对象索引

Question

我很难弄清楚如何通过下面的递归 binarySearch 函数 return 数组中项目的索引：

public static <AnyType extends Comparable<AnyType>> int binarySearch
      (AnyType[] a, AnyType x)
{
    int nMin = 0;
    int nMax = a.length - 1;
    int nMid = (nMin + nMax) / 2;

    int compare = a[nMid].compareTo(x);
    if(compare == 0)
        return 1;
    else if(compare == 1)
        return binarySearch(Arrays.copyOfRange(a, 0, a.length/2), x);
    else
        return binarySearch(Arrays.copyOfRange(a, a.length/2, nMax), x);
}

要求是写一个BS函数，带函数头，不要修改。我的函数工作正常，但是，当我通过每个递归级别修改数组时，我丢失了原始索引。我们还需要 return 我们正在搜索的项目的索引。我的实现总是 return 1.

是否可以在不创建另一个方法并从 binarySearch 函数中调用它的情况下执行此操作？

Answer 1

通过复制数组的递归搜索对性能不利。

递归传递整个数组，并附加范围值，即要处理的 start/end 个索引。

这样速度更快，并且还可以让您立即知道找到的元素的实际索引，因为索引值没有改变。

更新

如果无法更改方法签名，则需要进行一些更改：

int compare = a[nMid].compareTo(x);
if(compare == 0)
    return 1;

如果索引 nMid 处的元素相等，那是 return 的索引，而不是 1.

else if(compare == 1)
    return binarySearch(Arrays.copyOfRange(a, 0, a.length/2), x);

compareTo()return一个"positive integer"，不一定是1，所以test应该是compare > 0.

此外，不需要 else 部分，因为 if 具有无条件的 return.

else
    return binarySearch(Arrays.copyOfRange(a, a.length/2, nMax), x);

首先，copyOfRange()的最后一个参数是互斥的，所以需要是a.length，而不是nMax。

由于递归调用传递的范围不是从 0 开始，任何索引值 returned 都必须偏移，即 return binarySearch(...) + a.length/2.

同样，不需要 else。

除了以上所有内容，如果值不存在，代码最终会失败，因为copyOfRange()会创建一个空数组，代码不会' 处理它，导致值为 0 的 a[nMid] 抛出 IndexOutOfBoundsException。需要添加代码来处理。

Answer 2

因此，在几乎整个 300 名学生 class 非常困惑之后，老师在讲座中解决了这个问题，并解释说我们实际上可以创建另一个函数来处理我们需要的任何东西（在这种情况下位置).

所以我所做的只是编写一个普通的递归二进制搜索实现，并从教授要求包含的函数中调用它。

public static <AnyType extends Comparable<AnyType>> int binarySearch
      (AnyType[] a, AnyType x)
{
    return binarySearch(a, x, 0, a.length);
}

public static <AnyType extends Comparable<AnyType>> int binarySearch
      (AnyType[] a, AnyType x, int nMin, int nMax)
{
    if(nMin < nMax)
    {
        int nMid = nMin + (nMax - nMin) / 2;
        if(x.comapreTo(a[nMid]) == -1)
            return binarySearch(a, x, nMin, nMid);
        else if(x.compareTo(a[nMid]) == 1)
            return binarySearch(a, x, nMid+1, nMin);
        else
            return nMid;
    }
    rteurn -(nMin + 1);
}

另外，作为旁注，我认为我最初的问题措辞不当。我不是在寻找问题的解决方案，我或多或少是在寻找确认问题是不可能的。

递归二进制搜索和 return 对象索引

Recursive binary search and return index of object

java

recursion

binary-search