binarySearch方法抛出ArrayIndexOutOfBounds异常 - Java

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++;
}