Microsoft MVP성태의 닷넷 이야기
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일
 

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 이상이 되어야 하는데, 원소의 수가 230(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));
}




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







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

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 작성자
 




1  2  [3]  4  5  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
13922정성태5/3/20252857스크립트: 73. 파이썬 - Windows embeddable package 버전에서 tkinter 환경 구성
13921정성태5/3/20253412오류 유형: 952. 듀얼 채널 메모리 정렬을 지키지 않은 컴퓨터의 Windows 비정상 종료 현상(Blue Screen) [2]
13920정성태5/3/20253458오류 유형: 951. Typed DataSet 생성 중 "Failed to open a connection to the database" 오류
13919정성태5/2/20252853VS.NET IDE: 201. C# - Typed DataSet(XSD)를 위한 연결 문자열 암호화 [1]파일 다운로드1
13918정성태5/2/20253590VS.NET IDE: 200. C# - app.config 파일의 출력을 Configuration(Debug/Release)에 따라 제어하는 방법파일 다운로드1
13917정성태4/30/20252542VS.NET IDE: 199. Directory.Build.props에 정의한 속성에 대해 Condition 제약으로 값을 변경하는 방법
13916정성태4/23/20252088디버깅 기술: 221. WinDbg 분석 사례 - ASP.NET HttpCookieCollection을 다중 스레드에서 사용할 경우 무한 루프 현상 - 두 번째 이야기
13915정성태4/13/20253844닷넷: 2331. C# - 실행 시에 메서드 가로채기 (.NET 9)파일 다운로드1
13914정성태4/11/20254328디버깅 기술: 220. windbg 분석 사례 - x86 ASP.NET 웹 응용 프로그램의 CPU 100% 현상 (4)
13913정성태4/10/20252451오류 유형: 950. Process Explorer - 64비트 윈도우에서 32비트 프로세스의 덤프를 뜰 때 "Error writing dump file: Access is denied." 오류
13912정성태4/9/20252243닷넷: 2330. C# - 실행 시에 메서드 가로채기 (.NET 5 ~ .NET 8)파일 다운로드1
13911정성태4/8/20252837오류 유형: 949. WinDbg - .NET Core/5+ 응용 프로그램 디버깅 시 sos 확장을 자동으로 로드하지 못하는 문제
13910정성태4/8/20252876디버깅 기술: 219. WinDbg - 명령어 내에서 환경 변수 사용법
13909정성태4/7/20254376닷넷: 2329. C# - 실행 시에 메서드 가로채기 (.NET Framework 4.8)파일 다운로드1
13908정성태4/2/20254742닷넷: 2328. C# - MailKit: SMTP, POP3, IMAP 지원 라이브러리
13907정성태3/29/20254792VS.NET IDE: 198. (OneDrive, Dropbox 등의 공유 디렉터리에 있는) C# 프로젝트의 출력 경로 변경하기
13906정성태3/27/20254867닷넷: 2327. C# - 초기화되지 않은 메모리에 접근하는 버그?파일 다운로드1
13905정성태3/26/20254854Windows: 281. C++ - Windows / Critical Section의 안정화를 위해 도입된 "Keyed Event"파일 다운로드1
13904정성태3/25/20253981디버깅 기술: 218. Windbg로 살펴보는 Win32 Critical Section파일 다운로드1
13903정성태3/24/20252892VS.NET IDE: 197. (OneDrive, Dropbox 등의 공유 디렉터리에 있는) C++ 프로젝트의 출력 경로 변경하기
13902정성태3/24/20253589개발 환경 구성: 742. Oracle - 테스트용 hr 계정 및 데이터 생성파일 다운로드1
13901정성태3/9/20253916Windows: 280. Hyper-V의 3가지 Thread Scheduler (Classic, Core, Root)
13900정성태3/8/20255001스크립트: 72. 파이썬 - SQLAlchemy + oracledb 연동
13899정성태3/7/20253159스크립트: 71. 파이썬 - asyncio의 ContextVar 전달
13898정성태3/5/20254005오류 유형: 948. Visual Studio - Proxy Authentication Required: dotnetfeed.blob.core.windows.net
13897정성태3/5/20255211닷넷: 2326. C# - PowerShell과 연동하는 방법 (두 번째 이야기)파일 다운로드1
1  2  [3]  4  5  6  7  8  9  10  11  12  13  14  15  ...