二分探索：四つの選択、十六通りのループ

コード中の四つの選択は、いずれも慎重なプログラマーが検討すべきものです。どちらの選択肢も一見もっともらしく見えます。結果の下にある表では、十六通りのループを、12要素までの全配列と全探索値、計169ケースで試します。すべてに正解するのは二通りだけです。残るループはどれも二要素以下の配列で失敗し、十四通り中十三通りは一要素か空の配列で破綻します。検査範囲を1要素にすると三通りが残り、2要素では正しい二通りだけになります。256要素まで広げても、最初の失敗ケースは一つも動きません。この小さなケース群は標本ではなく、完全な検査です。ループが配列の値に対して行うことは、xとの比較だけだからです。異なる数からなる長さnの整列済み配列は、値を1、3、5…とした配列と同じように振る舞います。探索値の位置は、要素上か要素間の隙間にある2n + 1通りで、判定欄はそのすべてを試します。Jon BentleyはProgramming Pearlsで、この難しさを二つの年によって示しています。「最初の二分探索は1946年に発表されたが、nのすべての値に対して正しく動く二分探索が現れたのは1962年だった。」

末尾を見落とすを押してください。hi = n − 1でlo < hiを使うと、loとhiが重なった時点で止まり、その位置の要素を読みません。どの更新でもxは探索範囲内に保たれ、midがhiに達することはないため、読み落としうるのはhiの初期位置にある要素、つまり末尾だけです。それ以外の要素は、どの配列でも見つかります。配列外を読むを押すと、ちょうど逆の誤りが見られます。hi = nとlo <= hiの組合せではa[n]が探索範囲に入り、全要素より大きい探索値だけがloをそこまで進めます。256要素まででは、二つのループは全66,049ケース中それぞれ256ケースと257ケースを誤ります。256要素の配列だけなら、該当する探索値は0.19%です。この配列で探索値を百回無作為に選んでも、通常はどちらのバグも見つかりません。二つ目のループは空配列の唯一のケースで、一つ目は一要素の配列で見抜けます。JavaScriptでは、二つ目のループが偶然正しい答えを返すことさえあります。a[n]はundefinedとなり、それとの比較はどちらも偽です。そこでループはhi = mid − 1とし、正しく−1を返します。同じ読み出しをJavaで行えば例外が発生し、Cでは動作が未定義です。

JDKのループは表の先頭行にあり、判定欄で試せる全ケースに正解します。Joshua Blochがjava.util.Arraysのために書いたループです。Javaではlo + hiが32ビットのintとして計算され、2,147,483,647を越えると負数に回り込みます。2004年5月11日にSunへ提出されたバグ報告では、1,100,000,000バイトの配列の末尾要素を探索したところ、ArrayIndexOutOfBoundsException: -1064671149が発生しました。オーバーフロー表は、配列を確保せずに同じ探索を再現します。6回目にはlo + hiが2,165,624,999となり、回り込みとシフトの結果、中央値は報告どおり−1,064,671,149になります。同じ回でも、lo + ((hi − lo) >> 1)なら1,082,812,499です。報告の題名には、1<<30より大きな配列で探索が失敗するとあります。この境界は厳密です。1,073,741,824を入力すると、lo + hiの最大値は2³¹ − 2で収まります。要素が一つ増えるだけで、31回目にオーバーフローします。Blochが2006年にこのバグについて書いた記事によれば、バグは「九年ほど」潜んでいました。Programming Pearlsで正しさを証明されたBentley自身のコードにも、同じ問題があります。Bentleyの「mをlとuの平均とし、端数を切り捨てて最も近い整数にする」という記述は、数学上の整数には正しくても、32ビット整数には当てはまりません。