3

この再帰的な方法を反復に変換しようとしていますが、私の本では十分に説明されていないため、少し行き詰まっています。このメソッドは、特定の値の 2 つの値の間の配列を検索し、インデックスを返します。正しい方向への助けやポイントをいただければ幸いです。

public static int binarySearch(int anArray[], int first, int last, int value) {
    int index;

    if (first > last) {
        index = -1;
    } else {
        int mid = (first + last) / 2;

        if(value == anArray[mid]) {
            index = mid;
        } else if(value < anArray[mid]) { //Point x
            index = binarySearch(anArray, first, mid - 1, value);
        } else { //Point Y
            index = binarySearch(anArray, mid + 1, last, value);
        }
    }

    return index;
}
4

4 に答える 4

6

この例では、実際には非常に簡単な変換です。基本的に、再帰呼び出しを行うのではなく、全体をループでラップし、パラメーターを変更するだけです。

関数に複数の再帰呼び出しがある状況 (ツリーのトラバースなど) では、はるかに複雑になります。ただし、この場合、反復バージョンと再帰バージョンはほとんど同じです。

public static int binarySearch(int anArray[], int first, int last, int value) {

    do {
        if (first > last) {
            return -1;
        } else {
            int mid = (first + last) / 2;

            if(value == anArray[mid]) {
                return mid;
            } else if(value < anArray[mid]) { //Point x
                last = mid - 1;
                //index = binarySearch(anArray, first, mid - 1, value);
            } else { //Point Y
                first = mid + 1;
                //index = binarySearch(anArray, mid + 1, last, value);
            }
        }
    }
    while(true);
}
于 2012-09-17T23:13:14.180 に答える
3

これは、テール コールがあるときに実行できます。それを考慮してください

int f(int x, int y) {
  if (x == 0) { return y; }
  return f(y - 1, x);
}

と同等です

int f(int x, int y) {
  while (true) {
    // The body of your method goes here as normal.
    if (x == 0) { return y; }
    // Instead of returning the result of a recursive call though,
    // compute the parameters to tail call
    int newX = y - 1;
    int newY = x;
    // overwrite parameters with values to tail call
    x = newX;
    y = newY;
    // let the loop jump us back to the top of the method.
    continue;  // You can put continue in place of return
  }
}

メソッドが他のメソッドを呼び出す場合、これらは意味的に完全に同等ではありません。これは、Java がコール スタック イントロスペクションを許可しているためですが、コール スタックが呼び出し先と異なる結果として問題が発生する可能性は低いです。の代わりに無限ループが得られますStackOverflowError。

于 2012-09-17T23:10:02.153 に答える
3

このようにします。引数を特定し、それらをループ変数にします。関数を呼び出す代わりに、変数を更新します。関数から戻る代わりに、ループを終了します。

public static int binarySearch(int anArray[], int first, int last, int value) {
  int index;
  int done = 0;              // LOOP CONTROL

  while (done == 0) {        // A LOOP:

    if (first > last) {
        index = -1;          // RETURN ---> EXIT FROM LOOP
        done = 1;
    } else {
        int mid = (first + last) / 2;

        if(value == anArray[mid]) {
            index = mid;     // RETURN ---> EXIT FROM LOOP
            done = 1;
        } else if(value < anArray[mid]) { //Point x
            // index = binarySearch(anArray, first, mid - 1, value);
            // CALL ---> UPDATE THE VARIABLES
            last = mid-1;
        } else { //Point Y
            // index = binarySearch(anArray, mid + 1, last, value);
            // CALL ---> UPDATE THE VARIABLES
            first = mid+1;
        }
    }
  } // END LOOP

  return index;
}
于 2012-09-17T23:15:15.837 に答える
0

このメソッドの最初の呼び出しでfirst=0、last=anArray.length.

そこから始めて、私は次のことを提案します

public static int binarySearch_iterative(int[] anArray, int value) {
    int first, last, mid, index;
    first = 0;
    last = anArray.length - 1; // The last cell of the array

    while(first <= last) {
        mid = (first + last) / 2;
        if(anArray[mid] == value) {
            index = mid;
            break;
        } else {
            if(value < anArray[mid]) {
                last = mid;
            } else {
                first = mid;
            }
        }
        if(first > last) {
            index = -1;
            break;
        }
    }
    return index;
}

これがお役に立てば幸いです。

于 2012-09-17T23:12:56.543 に答える