java - 自定义二分搜索中的 ArrayIndesOutOfBoundsException？

Question

我正在尝试用 Java 实现二分搜索:

import java.util.Scanner;

public class Search 
{
public static void sequential_search(int[] array,int search_variable)
{
    boolean flag = false;
    for(int loop=0;loop<array.length;loop++)
    {
        if(array[loop] == search_variable)
        {
            flag = true;
            break;
        }
    }
    if(flag == true)
        System.out.println("The value is present");
    else
        System.out.println("The value is absent");
}

public static int binary_search_recursive(int[] array,int low,int high,int search_variable)
{
    if(low > high)
    {
        return 0;
    }
    else
    {
        int mid;
        mid = (low+high)/2;
        if(array[mid] == search_variable)
        {
            return 1;
        }
        else if (array[mid] > search_variable)
        {
            return binary_search_recursive(array, low, mid - 1, search_variable);
        }
        else 
        {
            return binary_search_recursive(array, mid + 1, high, search_variable);
        }
    }
}

public static void main(String[] args) 
{
    int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int search_variable;

    System.out.println("Please enter the number to be search:");
    Scanner number = new Scanner(System.in);
    search_variable = number.nextInt();
    System.out.println("The number to be searched is "+search_variable);

    //sequential_search(array,search_variable);

    if ((binary_search_recursive(array, 0, array.length, search_variable)) == 0)
        System.out.println("The value is present");
    else
        System.out.println("The value is absent");

}

}

当我输入算法未找到的术语时，当我退出 ArrayOutOfBoundsException 时，我会感到困惑。

Please enter the number to be search:
12
The number to be searched is 12
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
    at Search.binary_search_recursive(Search.java:32)
    at Search.binary_search_recursive(Search.java:42)
    at Search.binary_search_recursive(Search.java:42)
    at Search.binary_search_recursive(Search.java:42)
    at Search.main(Search.java:59)

对此的任何意见都会有所帮助。 谢谢:)

Answer 1

我认为这里的问题是您的 low 和 high 变量表示范围 [low, high)，其中 high 值排除。这意味着您的基本情况目前是

if(low > high)
{
    return 0;
}

应该是

if(low >= high)
{
    return 0;
}

因为如果你的范围是 [low, low)，那么就没有任何元素了。在终止之前要求 low > high 意味着您需要 low 来实际超过 high，这是不可能的。

如果我的说法是正确的，这也意味着您对该函数的递归调用之一具有错误的上限。具体来说，这段代码:

    else if (array[mid] > search_variable)
    {
        return binary_search_recursive(array, low, mid - 1, search_variable);
    }

应该是

    else if (array[mid] > search_variable)
    {
        return binary_search_recursive(array, low, mid, search_variable);
    }

因为如果 high 是独占的，则传入 mid 作为上限是使所有内容达到但不包括中间值的正确方法。

希望这有帮助!