충격! 거의 모든 이진 검색과 병합 정렬이 깨졌습니다

Google 소프트웨어 엔지니어 Joshua Bloch는 JDK와 Jon Bentley의 'Programming Pearls' 모두에서 발견된 거의 20년 동안 잠복해 있던 이진 검색 알고리즘 버그를 밝혀냈습니다! 이 버그는 `int mid = (low + high) / 2;` 라인에서 발생하며, low와 high의 합이 최대 양수 정수 값을 초과하면 정수 오버플로우가 발생하여 배열 범위를 벗어나는 예외가 발생합니다. 이 버그는 대규모 데이터 세트에서만 발생하기 때문에 오늘날의 빅데이터 시대에 특히 위험합니다. 이 기사에서는 몇 가지 수정 방법을 살펴보고 엄격한 테스트와 증명을 거쳤더라도 버그가 남아 있을 수 있다는 점을 강조하며 프로그래머에게 주의 깊고 겸손해야 함을 촉구합니다.