0

ウィキペディアから取得した以下の補間検索を使用する Java プログラムを作成しています。私のメイン プログラムでは、100,000 スポットを持つ int 配列を作成しました。次に、それらすべてのスポットを乱数で埋めて並べ替えます。次に、ランダムな検索キーを生成し、関数を呼び出します。また、異なる検索キーを使用して、関数呼び出しを毎回 100 回ループしています。これを行うと、このステートメント if (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

2,147,483,647のintに格納できる最大値がオーバーフローしています。

方程式の分子を計算するときは、（（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] == sortArray [high]==toFindという状況になります。

次に、方程式は次のようになります。

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

Javaではゼロによる除算が可能です。何が起こるかは正確にはわかりませんが、この場合はmid=infinityまたはNaNである可能性があります。

于 2012-10-06T02:30:29.920 に答える