0

我正在制作一个使用下面我从维基百科获得的插值搜索的 java 程序。在我的主程序中，我创建了一个包含 100,000 个点的 int 数组。然后我用随机数填充所有这些点并对其进行排序。然后我生成一个随机搜索键并调用该函数。我还每次使用不同的搜索键循环函数调用 100 次。当我这样做时，如果（sortedArray [mid] < toFind），我在这个语句上得到一个数组越界错误。该程序适用于具有 10 个点、100 个点、1000 个点的数组，但是当我达到 100,000 个时，我得到了错误。你知道我能做些什么来解决这个问题吗？

 public int interpolationSearch(int[] sortedArray, int toFind){
  // Returns index of toFind in sortedArray, or -1 if not found
  int low = 0;
  int high = sortedArray.length - 1;
  int mid;

  while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
   mid = low +
         ((toFind - sortedArray[low]) * (high - low)) /
         (sortedArray[high] - sortedArray[low]);  

   if (sortedArray[mid] < toFind)
    low = mid + 1;
   else if (sortedArray[mid] > toFind)
    // Repetition of the comparison code is forced by syntax limitations.
    high = mid - 1;
   else
    return mid;
  }

  if (sortedArray[low] == toFind)
   return low;
  else
   return -1; // Not found
 }
4

2 回答 2

0

您应该在像 Eclipse 这样的 IDE 中开发这样的代码（还有其他的）。在 Eclipse 中，您可以调试此程序并指示调试器在抛出特定异常（如 ArrayOutOfBoundsException）时停止。然后，您可以查看导致错误的代码行，并且可以查看每个变量的值。有了这些信息，识别和解决问题就会容易得多。

于 2012-10-06T02:26:09.507 回答
0

您正在溢出可以存储在 int 中的最大值，即 2,147,483,647。

在计算方程式中的分子时，您正在执行 ((39258-0)*(99999-0))，即 3,925,760,742。

如果您将其更改为此，您将不会遇到此问题：

long numerator = (long)(toFind - sortedArray[low]) * (long)(high - low);
mid = low + numerator / (sortedArray[high] - sortedArray[low]);

我认为您还需要将 while 循环更改为：

while (sortedArray[low] < toFind && sortedArray[high] >= toFind) {

否则你会遇到 sortedArray[low] == sortedArray[high] == toFind

然后你的方程减少到

mid = low + (0 * (high - low)) / 0 = 0/0

Java 允许除以零。我不确定会发生什么，在这种情况下可能是 mid = infinity 或 NaN。

于 2012-10-06T02:30:29.920 回答