java - 二进制搜索在 Java 中给出 Index Out of Bound 异常

Question

我正在尝试使用 java 编程语言实现二进制搜索。很明显，应该对数组进行排序以便使用二分查找，因为它使用分而治之的概念。当元素在数组内和不在数组内时，代码都适用于这两种情况。但是，当我输入一个大于数组中最大数字的数字时，程序将崩溃并给出索引超出范围异常。

public class Binary {

public static void search(int arr[]) {
    Scanner in = new Scanner(System.in);
    int upper = arr.length;
    int lower = 0;
    int middle = 0;
    int flag = 0;
    int key;

    /*
     * flag = 0 ---> not found yet.
     * flag = 1 ---> element is found.
     * flag = 2 ---> no such element.
     */

    System.out.println("Enter the number that you want to find... ");
    key = in.nextInt();

    while (flag == 0) {
        middle = (int) (lower + upper) / 2;

        if (key == arr[middle]) {
            flag = 1;
        }

        if (key < arr[middle]) {
            upper = middle - 1;
        } else if (key > arr[middle]) {
            lower = middle + 1;
        }
        if (lower > upper) {
            flag = 2;
        }
    }
    if (flag == 1) {
        System.out.println(arr[middle] + " has been found, its index is: "
                + middle);
    } else
        System.out.println("Error, no such element.");
}

public static void main(String[] args) {

    int arr[] = { 2, 4, 6, 8, 11, 34, 56 };
    search(arr);
}

Answer 1

这应该可以解决您的问题

int upper = arr.length-1;

如果您正在寻找一个大于最大数的数字，那么您肯定会查看数组的最后一个元素。但是在您的代码中，upper 的初始值比最后一个元素的索引多 1。