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

2

您的代码很好，您只是错误地传递了值。您可能使用了错误的 highPos 来启动您的方法，如果是这种情况，请使用 myArray.length -1 而不是 myArray.length。

否则，您对修改后的方法的参数调用完全错误，可能会切换值。调用代码应如下所示。

binarySearch(myArray, myIntToSearchFor, 0, myArray.length-1)
于 2013-06-06T16:35:35.200 回答
1

我相信您正在传递array.length而不是array.length - 1作为highPos.

于 2013-06-06T16:36:29.157 回答