[알고리즘] 이분탐색과 오버플로우 버그

버그 설명

아래는 C언어로 구현한 Binary Search 함수이다.

/* n: length of arr */
int binarySearch(const int arr[], int n, int key) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = arr[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

위 코드는 일반적으로 잘 동작하지만, 오버플로우 버그가 발생할 수 있다.

int mid = (low + high) / 2;

바로 이 부분 때문이다. 만약 low + high 값이 int 자료형 범위를 넘어간다면 오버플로우가 발생하여 올바른 값이 mid에 할당되지 않는다.

---

해결 방법

int mid = (low + high) / 2;

위 코드를 아래와 같이 바꾼다.

int mid = low + (high - low) / 2;

또는

int mid = ((unsigned int)low + (unsigned int)high)) >> 1

---

알고리즘 문제 적용

[Python] 백준 20444 - 색종이와 가위 풀이

---

참고자료

참고: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html