JMBook에서 반복문불변식에 대한 질문입니다~

  • cdragon
    cdragon

    안녕하세요~ 알고리즘을 잘해보구 싶어서 종만님의 JMBook을 구독해서 열심히 읽고있는 애독자입니다~ 정말 좋은 책 감사드려요 ^^

    다름이 아니구 반복문불변식 부분을 읽다보니, 궁금한점이 생겨서요..
    이진탐색과 반복문불변식 부분에서, 만약 이진탐색코드가 다음과 같이 되어있다면,
    반복문불변식은 어떻게 세워야 할까요?

    bool bFind = false;

while (lo < hi)
{
    int mid = (lo+hi)/2;
    if (A[mid] == x) {
        bFind = true;
        break;
    }
    else if (A[mid] < x) {
        lo = mid;
    }
    else {
        hi = mid;
    }
}

if (bFind == true) {
    return mid;
}
else {
    return -1;
}

    11년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    A[lo] < x < A[hi] 가 아닐까요?
    따라서 반복문 진입 전에 lo나 hi가 x와 같은지 확인하셔야겠죠. 이게 번거로우시면 A[lo] <= x < A[hi] 같은 불변식을 유지하시면 되고요. ^^


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.