二进制搜索在 Java 中给出索引越界异常

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。

Answer 2

您可以采用MisterDev 的解决方案并更正上界。通常，在 Java 数组中，下限是包容性的，上限是独占性的，但是，我喜欢 lower 和 upper 遵循这种模式的想法。

那么，lower < upper表示区间不为空，前半部分继续查找时，中间点将成为新的排他上界：

public static int search(int arr[], int key)
{
    int upper = arr.length;
    int lower = 0;

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

        if (key == arr[middle]) return middle;

        if (key < arr[middle]) {
            upper = middle;
        } else if (key > arr[middle]) {
            lower = middle + 1;
        }
    }

    return -1;
}

我已经让函数将键作为参数，return 索引或 -1 如果找不到键。在我看来，获取用户输入和 flag 与您的代码无关；你应该为此写一个包装器，这样 Binary.search 就真的可以进行搜索了。

二进制搜索在 Java 中给出索引越界异常

Binary Search gives Index Out of Bound Exception in Java

java

arrays

algorithm

search

binary