3

我正在尝试将这种递归方法转换为迭代方法，但我有点卡住了，因为我的书解释得不够多。此方法在两个值之间的数组中搜索特定值并返回索引。任何帮助或正确方向的观点将不胜感激。

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

你这样做。识别参数并将它们变成循环变量。不要调用函数，而是更新变量。而不是从函数返回 - 从循环中退出：

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 回答
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 允许调用堆栈自省，但由于调用堆栈与被调用者不同，您不太可能遇到问题——这是您最可能遇到的问题into 是你会得到一个无限循环而不是一个StackOverflowError.

于 2012-09-17T23:10:02.153 回答
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 回答