カスタムバイナリ検索で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変数が除外さhigh値は、範囲[低、高）を表していることだと思います。これは、あなたが）[低、低域を持っている場合は、左のいずれかの要素が存在しないためであるあなたのベースケースは、現在

if(low > high) 
{ 
    return 0; 
} 

はおそらく

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

なければならないことを意味しています。終了する前にlow > highを要求すると、実際にはhighを下回る必要がありません。

私はこのことについて正しく、これは、関数への再帰呼び出しの1つが間違った上限を持っていることを意味します。具体的には、このコード：highが排他的であれば、上限としてmidに渡すと、中間値を含むすべてのものまでではなくを取得するための適切な方法であるため、

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

でなければなりません。

希望すると便利です。

Answer 2

if ((binary_search_recursive(array, 0, array.length, search_variable)) == 0) 

これらの引数を使用すると、結局array [array.length]を確認しています。 10要素はarray.lengthが10であることを意味しますが、10番目のインデックスはもちろん未定義です。

if ((binary_search_recursive(array, 0, array.length-1, search_variable)) == 0)