반복을 반복으로 변환

Question

이 반복적 인 방법을 반복으로 변환하려고하는데 내 책에서 충분히 설명하지 못하므로 조금 꼼짝하지 않습니다. 이 메서드는 특정 값에 대한 두 값 사이의 배열을 검색하고 인덱스를 반환합니다. 어떤 도움이나 올바른 방향으로 향한 점이 인정 될 것입니다.

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; 
} 

Answer 1

꼬리 전화를 받았을 때 가능합니다.

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

이

자바 Call stack introspection 수 있지만의 결과로 문제로 실행 가능성이기 때문에 당신의 방법은 다른 방법을 호출 할 때이 매우 의미 동등하지 않은

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 
    } 
} 

에 해당하는 것을 고려 호출 스택이 호출 수신자와 다른 경우 - 가장 큰 문제는 StackOverflowError 대신 무한 루프가 발생한다는 것입니다.

Answer 2

이 메서드의 첫 번째 호출에서 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; 
} 

을 제안한다.

Answer 3

이 예에서는 실제로 매우 쉽게 전환됩니다. 기본적으로 루프 전체를 감싸고 재귀 호출을 작성하는 대신 매개 변수를 수정하면됩니다.

트리에서 트래버스하는 것과 같이 여러 개의 재귀 호출이있는 상황에서는 훨씬 더 복잡해집니다. 그러나이 경우 반복 버전과 재귀 버전은 거의 동일합니다.

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); 
} 

Answer 4

이렇게하면됩니다. 인수를 식별하여 루프 변수로 만드십시오. 함수를 호출하는 대신 변수를 업데이트하십시오. 루프에서 function-exit에서 돌아 오는 대신 :

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; 
}