実装上の間違い

ウィキペディア小見出し辞書

実装上の間違い

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/26 14:35 UTC 版)

「二分探索」の記事における「実装上の間違い」の解説

ドナルド・クヌースは "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky ..."（二分探索の基本的なアイディアは比較的平易だが、その詳細は驚くほど扱いが難しいものになりうる）と述べており、二分探索が正確に実装されていないことは多い。Richard E. Pattis の1988年の調査では、書籍20冊のうち15冊が誤っていた。 よくある間違いの一つは、上記のC言語のコードで imin + (imax - imin) / 2 を (imax + imin) / 2 としてしまう事である。(imax + imin) / 2 では、imax + imin が int の値の上限 (INT_MAX) を超えて不正な値になってしまう可能性がある。（imax + imin が INT_MAX を超える可能性が全くないと保証できる場合は問題ない。）Java の標準ライブラリの Arrays.binarySearch() では JDK 1.2 (1998年) から間違えており、Java 6 (2006年) で修正された。なお、このバグについてクヌースは、自分が気がついていなかったパターンだと、あるインタビューの際に述べている（書籍『Coders at Work』にて。オーム社から出ている邦訳では567ページにある）。