半分ずつ探す（二分探索）

1,000,000個の中から1つ見つけるのに、1個ずつ調べると最悪1,000,000回。 半分ずつ捨てていくと20回です。 その20回を、実際に数えてみてください。

1,000,000個から20回。1個ずつなら1,000,000回です

ここがこのページで一番言いたいところです。 探すものが1,000,000個あるとき、はしから1個ずつ調べると、運が悪ければ1,000,000回見ることになります。真ん中を見て半分を捨てるやり方なら、どんなに運が悪くても20回です。

なぜ20回で足りるのか。2を20回かけると1,048,576になり、1,000,000を追い越すからです。 1回聞くごとに区別できる数が2倍になるので、20回で1,048,576通りまで見分けられる、という勘定になります。

いちばん右の列が、その回数で足りることの検算です。 どの行も左の個数より大きくなっていることを確かめてください。 単体テストが全部の行についてこれを見ています。1,000,000個の行には左に帯を付けてあります（色だけで示さないためです）。

候補は、こう減っていきます

1,000,000個から始めて、真ん中を1つ見るたびに悪いほうに転んだとしていくつ残るかを並べると、こうなります。

1,000,000 → 500,000 → 250,000 → 125,000 → 62,500 → 31,250 → 15,625 → 7,812 → 3,906 → 1,953 → 976 → 488 → 244 → 122 → 61 → 30 → 15 → 7 → 3 → 1 → 0

矢印は20本、つまり20回で残り0個になりました。 残りが0になるということは、それより前に必ず見つかっているということです。 最後のほうを見てください。1000個を切ってから0になるまで、たった10回です。大きい数ほど、この差が効いてきます。

ただし「並んでいること」が要ります

半分を捨てられるのは、「真ん中より大きいなら、小さい側は全部いらない」と言い切れるからです。 これは小さい順に並んでいるからこそ言えることで、 ばらばらに置かれた数には使えません。

国語辞典を思い出してください。まん中あたりを開いて「た」が出たら、 「さ」を探している人は後ろ半分を丸ごと閉じられます。 これができるのは、辞典が五十音順に並んでいるからです。 単語がばらばらに載っている本では、1ページずつめくるしかありません。

だから1回しか探さないなら、並べ替えてから探すのは損です。 並べ替えるほうが1個ずつ探すより手間がかかります。 何度も探すもの（辞書・名簿・索引）だからこそ、先に並べておく値打ちが出ます。

じつは「正しく書くのが難しい」ことで有名なアルゴリズムです

考え方はこれだけ単純なのに、二分探索は正しく書くのが難しいアルゴリズムとして知られています。 ジョシュア・ブロックが2006年6月2日にグーグルの研究ブログに書いた記事Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken（新しいタブで開きます）（およそ「大ニュース ── 二分探索とマージソートは、ほとんど全部が壊れている」）に、 こうあります。

While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962.（訳）最初の二分探索が世に出たのは1946年だが、あらゆる n について正しく動く二分探索が現れたのは1962年だった。

16年かかっているわけです。 しかも話はそこで終わりません。 ブロック自身がJava の標準ライブラリ（java.util.Arrays）に書いた二分探索にも 同じ間違いが入っていました。同じ記事に、after lying in wait for nine years or so（およそ「9年ほど潜んだのち」）に、誰かのプログラムを壊してはじめて報告された、とあります。 同じ不具合は、ジョン・ベントリーの有名な教科書『珠玉のプログラミング（Programming Pearls）』にも載っていました。

まん中を求める足し算が、あふれます

壊れていたのは、たった1行です。まん中を求めるところでした。

int mid = (low + high) / 2;

Java の int は32ビットの整数で、表せるいちばん大きい数は2,147,483,647です。 これを超えるといちばん小さい負の数へ回り込みます。 記事によれば、この不具合が出るのは要素数が2の30乗（およそ10億）以上の配列のときで、 そのとき Java は ArrayIndexOutOfBoundsException を投げます。

実際に見てみましょう。長さ2,147,483,647の並びを探している途中で、low が 1,073,741,824、high が 2,147,483,646になったとします。足すと3,221,225,470で、2,147,483,647を超えました。 正しいまん中は1,610,612,735のはずです。

合わない2行には、左に帯を付けてあります（✕の文字と帯の両方で示していて、色だけには頼っていません）。 いまの Java は符号なし右シフトで直してあります。 実際、OpenJDK のArrays.java（新しいタブで開きます）を開くと int mid = (low + high) >>> 1;と書かれています（この行はソースを開いて確かめました）。

JavaScript では事情が違います ── でも別の落とし穴があります

このページを動かしている JavaScript では、この足し算はあふれません。 JavaScript の数は64ビットの浮動小数点ひとつだけで、整数として正確に扱えるのは9,007,199,254,740,991までです。 いっぽう配列の長さの上限は4,294,967,295なので、 両はしの添字を足しても85億ほどにしかならず、 正確に扱える範囲にすっぽり収まっています。

そのかわり、JavaScript には別の注意があります。 割り算が小数を出すので切り捨て（Math.floor）を忘れると添字が小数になるのが1つ。 そしてビット演算子だけは、いったん32ビットに戻るのがもう1つです。 つまり Java の直し方を見て(low + high) >> 1 と書き写すと、あふれないはずの JavaScript でそこだけ壊れます（上の表の4行目がそれです）。

いちばん安全なのは、表のいちばん下のlow + (high - low) / 2です。引き算にすれば、そもそも大きい数を作らないので、どの言語でもあふれません。 この道具の中の計算も、この書き方にしてあります。

頭の中で決めた数は、どこにも送っていません

数当てゲームであなたが決める数は、どの欄にも打ち込みません。 「もっと大きい」「もっと小さい」を押しているだけです。 探す数を打ち込むほうの使い方でも、計算はすべてこの画面の中で終わります── どこかへ送ることも、保存することもありません。 ページを閉じれば何も残りません。

出どころ: 1946年と1962年の話、Java の標準ライブラリに9年潜んでいたこと、 2の30乗以上の配列で出ること、投げられる例外の名前は、いずれもジョシュア・ブロックの記事（Google Research Blog・2006年6月2日）（新しいタブで開きます）から取っています。 いまの Java がどう書いているかは OpenJDK のソースを開いて確かめました。 JavaScript の上限（9,007,199,254,740,991と4,294,967,295）は、 単体テストの中で実際に動かして確かめています。