Java 中的递归二进制搜索

Question

我不明白为什么下面的代码会返回 0。

首先，这是我的测试：

 @Test
public void testOddEntriesMatchRecursive() {
    int[] arr = new int[]{1,3,5};
    ...
    Assert.assertEquals(2, Chopper.chopRecursive(5, arr));
}

接下来，这是重要的实施部分：

static int chopRecursive(int toFind, int[] arr) {

    /* Empty array test */
    if (arr.length == 0) return -1;

    /* Calculate the midpoint */
    int midpoint = (arr.length) / 2;

    if (arr[midpoint] == toFind) {
        return midpoint;
    } else if (arr[midpoint] > toFind) {
        if (midpoint == 1) {
            if (arr[0] == toFind)
                return 0;
            else
                return -1;
        } else {
            return midpoint + chopRecursive(toFind, Arrays.copyOfRange(arr, 0, midpoint));
        }
    } else {
        return midpoint + chopRecursive(toFind, Arrays.copyOfRange(arr, midpoint, (arr.length - 1)));
    }
}

最后，这是我的测试结果：

java.lang.AssertionError: 
Expected :2
Actual   :0

Answer 1

您的问题可能与以下调用有关：

Arrays.copyOfRange(arr, midpoint, (arr.length - 1))

根据文档：

parameter to - the final index of the range to be copied, exclusive. (This index may lie outside the array.)

如果我将调用更改为：

Arrays.copyOfRange(arr, midpoint, arr.length)

它returns 2.

Java 中的递归二进制搜索

Recursive binary search in Java

java

recursion

binary-search