衝撃！ほぼすべての二分探索とマージソートが壊れている
2025-01-11
Googleのソフトウェアエンジニア、Joshua Bloch氏が、JDKとJon Bentleyの『プログラミング珠玉』の両方に見つかった、ほぼ20年間にわたって潜んでいた二分探索アルゴリズムのバグを明らかにしました！このバグは、`int mid = (low + high) / 2;`という行に起因し、lowとhighの合計が最大の正の整数値を超えると整数オーバーフローが発生し、配列の範囲外例外が発生します。このバグは、大規模なデータセットでのみ発生するため、今日のビッグデータ時代において特に危険です。この記事では、いくつかの修正方法を検討し、厳格なテストと証明を行った場合でもバグが残る可能性があることを強調し、プログラマーに注意深く謙虚であるよう促しています。