2의 30승 이상의 원소를 갖는 경우 버그가 발생하는 이진 검색(Binary Search) 코드

요 며칠 전에 재미있는 트윗을 하나 봤습니다. ^^

세상의 거의 모든 이진 검색, 머지 소트 구현에 버그가 있다고. 수십년 동안 잘 써왔지만, 요즘 들어 원소 개수가 10억개 넘는 경우 등이 생기면서 오동작이 발생한다는 얘기.
; https://twitter.com/roh0sun/status/757199922470858753

Nearly All Binary Searches and Mergesorts Are Broken (2006)
; https://twitter.com/roh0sun/status/757199922470858753

[Google Research Blog] Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken 
; https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

2006년도의 글인데, 그러니까 대부분의 이진 검색 코드에서 중간 위치를 결정하는 코드가 다음과 같이 되어 있을 텐데요.

int mid = (low + high) / 2;

low, high 변수의 타입이 signed integer이고 각각의 값이 2의 30승을 넘으면 오버플로우가 발생하게 됩니다. 따라서 mid의 값이 정상적인 값을 갖지 못하는 버그입니다. 이런 현상이 발생하는 경우는 (low + high)의 값이 Int32.MaxValue 이상이 되어야 하는데, 원소의 수가 2³⁰(1,073,741,823)개만 되어도 그렇게 됩니다. 왜냐하면 이진 검색의 특성상 우측으로 계속 재귀 호출이 되다 보면 low가 high의 값에 접근하기 때문입니다.

어쨌든 ^^ 구글다운 글입니다. 10억개의 데이터 정도는 우스울 테니.

블로그에서는 이를 완화하기 위해 다음의 코드를 제시합니다. (물론 완화입니다. 구글 정도되면 10억이나 20억이나 큰 차이는 없을 듯!)

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

(또는)

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

참고로, C#의 이진 검색 코드인 Array.BinarySearch 메서드를 보면 내부의 중간 위치 구하는 코드가 다음과 같이 되어 있습니다.

private static int GetMedian(int low, int hi)
{
    return (low + ((hi - low) >> 1));
}

---

[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[최초 등록일: 8/1/2016]
[최종 수정일: 5/26/2022]


이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

by SeongTae Jeong, mailto:techsharer at outlook.com