-1

我不知道为什么这个方法会抛出 ArrayIndexOutOfBounds 异常。

When I change the initial "high"值，我搜索"int high = array.length - 1;"的程序将。return any integer value

我究竟做错了什么？

提前致谢！

public class BinarySearch {

public static void main(String[] args) {

    int searchValue = 12;
    int[] givenNums = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    binarySearch(givenNums, searchValue);
    System.out.println("\nResult: " + searchValue);

}

public static int binarySearch(int[] array, int key) {
    int low = 0;
    int high = array.length;
    int mid = (low + high) / 2;
    int i = 0;
    System.out.println();

    while (low <= high) {
        System.out.print(i + " ");
        if (array[mid] < key) {
            low = mid + 1;
            mid = (low + high) / 2;
        } else if (array[mid] > key) {
            high = mid - 1;
            mid = (low + high) / 2;
        }
        else
            return mid;

        i++;
    }
    return -1;
}
}
4

3 回答 3

5

您需要对是否意味着它可以是包容性或排他性high的最大值保持一致。你从它是一个排他的上限开始：

int high = array.length;

但是，只有当它是一个包容性上限时，您的while循环条件才适用：

while (low <= high)

您可能应该将while条件更改为：

while (low < high)

...并更改high稍后的分配。

或者，您可以保持包容性，并将初始值更改为array.length - 1.

这将停止情况 where low == high == mid == array.length，这是它会爆炸的地方。

我还建议将mid = (low + high) / 2计算移动到循环中的第一个语句while- 然后你可以摆脱重复的代码。

while (low < high) {        
    mid = (low + high) / 2;
    System.out.print(i + " ");
    if (array[mid] < key) {
        low = mid + 1;
    } else if (array[mid] > key) {
        high = mid;
    }
    else {
        return mid;
    }
    i++;
}
于 2012-10-10T19:56:31.237 回答
3

数组的最大索引是array.length - 1从 0 开始。

于 2012-10-10T19:55:22.937 回答
1

java中的数组从0开始索引，这意味着...

int[] arr = 新的 int[10];

第一个值为 arr[0]，最后一个值为 arr[9]，长度为 10。

于 2012-10-10T19:56:49.060 回答