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
30(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));
}
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]