へ〜たのめも

Cafe Babe - binarySearchメソッドのバグ
Java API ライブラリの binarySearch に潜んでいたバグを Joshua Bloch が指摘した、という記事の紹介。バグ自体は、配列の真ん中を求める際に(足し算を先にしてしまって) int がオーバーフロー、これで負のインデックスが返って ArrayIndexOutOfException を喰らうというもの。もちろん、こんな大きな配列を sort する機会は少ないので、レア・ケースと言えばレア・ケース。

昔から「binary search アルゴリズムを一発で正しく実装できたら Knuth 並み」と言われるくらい binary search の正確な実装は難しい。奇妙なコーナーケースがいろいろあるのだ。で、「自分で作るのではなく、既に実績もあり、よくテストされていて、安全なライブラリを使いなさい」と言う話になるのだが、今回はそのライブラリと言えども完全というわけにはいかないよ、というお話。かなりの数の実装が同様のバグを抱えているようだ。