0

この教科書ページの例を見た後、再帰的二分探索を実装しようとしています。

ほとんどの場合、私のアルゴリズムは正常に機能しているように見えますが、配列内の最大値よりも高い値では、ArrayIndexOutOfBoundsException. 私のアルゴリズムと教科書の例を見ると、それらは同じように見えます。誰かが私が間違っている場所を見つけるのを手伝ってくれますか?

これはこのスレッドとほとんど同じ問題であることを認識しており、提案されている解決策を既に検討しています。しかし、サンプル コードではこのような引数の修正が実装されていません。

    public static int binarySearch(int[] array, int item, int lowPos, int highPos){
    if (lowPos > highPos){
        return -1;
    }

    int mid = (lowPos + highPos)/2;

    if (array[mid] == item){
        return mid;
    }else if (array[mid] > item){
        return binarySearch(array, item, lowPos, mid-1);
    }else{
        return binarySearch(array, item, mid+1, highPos);
    }
}

これは教科書の例であり、明らかにエラーは発生しません。

    static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {

   if (loIndex > hiIndex) {
         // The starting position comes after the final index,
         // so there are actually no elements in the specified
         // range.  The value does not occur in this empty list!
      return -1;
   }

   else {
         // Look at the middle position in the list.  If the
         // value occurs at that position, return that position.
         // Otherwise, search recursively in either the first
         // half or the second half of the list.
      int middle = (loIndex + hiIndex) / 2;
      if (value == A[middle])
         return middle;
      else if (value < A[middle])
         return binarySearch(A, loIndex, middle - 1, value);
      else   // value must be > A[middle]
         return binarySearch(A, middle + 1, hiIndex, value);
   }

} // end binarySearch()
4

2 に答える 2

1

への引数としてのarray.length代わりに渡していると思います。array.length - 1highPos

于 2013-06-06T16:36:29.157 に答える