古い記事
ランダムジャンプ
新しい記事
二分探索(バイナリサーチ)の
int mid = (low + high) / 2;
の計算でオーバーフローになる可能性。

404 Blog Not Found:(a+a)/2 == -a /* 半世紀もののバグ */
http://blog.livedoor.jp/dankogai/archives/50522708.html
確かにこれだけの大きさの配列をbsearchしたりsortしたりという状況はあまりなさそうですが、比較的身近な例ではsuffix arrayとかがこのケースにぶち当たりそうです。

とっくにぶち当たっていますよ。
suffix array のライブラリ SUFARY では対処済みです(前世紀)。
実装していた当時、GBサイズを扱う時にこれに悩まされて、結局両方を2で割ってから足すという回避策を採用しました。
見てみるとこんな感じ (sbr.* は long です)。
sbr.center = sbr.left / 2 + sbr.right / 2 + (1 & sbr.left & sbr.right);

って、この overflow の話って結構メジャーなのでは?
なんかの本に書いてあったような記憶があるのだが思い出せない…。
気のせいかも。

元ネタ:
Official Google Research Blog: Extra, Extra - Read All About It:
Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.com/2006/06/
extra-extra-read-all-about-it-nearly.html


関連:
- Cafe Babe - binarySearchメソッドのバグ
  http://d.hatena.ne.jp/kazama/20060605/p2
- 古典的バイナリサーチアルゴリズムにバグ: ホットコーナーの舞台裏
  http://iiyu.asablo.jp/blog/2006/06/05/393464
- Doblog - 日々礼賛 -
  http://www.doblog.com/weblog/myblog/42113/2611927#2611927
- バグとintと古典的アルゴリズム
  http://d.hatena.ne.jp/kappe1982/20060607#1149658236