binarySearch Method Throwing ArrayIndexOutOfBounds Exception

Question

我不知道为什么这个方法会抛出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;
}
}

Answer 1

您需要保持一致high表示它可以包含或排除的最大值。您从它是唯一的上限开始：

int high = array.length;

但是，您的while循环条件仅在包含上限时才适用：

while (low <= high)

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

while (low < high)

。并在以后更改high的分配。

或者，您可以将其保留为包含性，并将初始值更改为 array.length - 1 。

这将阻止这种情况 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++;
}

Answer 2

数组

的最大索引从 0 开始时array.length - 1。

Answer 3

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

int[] arr = new int[10];

第一个值是 arr[0]，

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