バグとintと古典的アルゴリズム

古典的バイナリサーチアルゴリズムにバグが見つかったというお話。
404 Blog Not Found経由で、ソース元はGoogle Researchらしい。

そのバグの内容はといえば、ピボットの選択の部分で

int mid = (low + high) / 2;

という処理がオーバーフローを起こすって話。

・・いや、なんていうか・・バグか？？

そりゃバグには違いないんだけどさ。
32bit platformであれば、MAX_INTが通常2^31-1ですから。
だから配列サイズが2^30を超える場合には上記のバグが発生する可能性はある。
確かにある。
けどなぁ。1Gだろ？配列サイズが。
そんな配列に対してbinary searchとか。。
Googleあたりではそんな処理をしてるってのは確かに興味深いし、
これまでずっと気づかなかったってのはショッキングではあるわけですが。
そもそもMAX_INTが2^31-1である以上、1Gを超えるサイズのモノをintで処理すればあちこちでオーバーフローが発生しそうな予感。

そして今度は配列サイズが2Gを超えた日には現状ほとんどのアルゴリズムが破綻するんじゃないですか？ひょっとすると。
少なくともインデクスをsigned intで処理してるアルゴリズムを32bitマシンで動かせば全滅って話ですよね。
なんかもう、大変ですねぇ。

ちなみに、提案されてる回避コードはこちら

int mid = low + ((high - low) / 2);

or

int mid = ((unsigned) (low + high)) >> 1;

いやー、エレガントですね。
こういうコードはまだまだパッと思いつけないです。