[を] 二分探索でオーバーフロー

二分探索でオーバーフロー

二分探索(バイナリサーチ)の

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

posted with Yasazon on 2006.06.09 [copy]