二分探索 (反復版)

並び替え済みの配列から値を探します。前回のように先頭から順に見ていくと、100 万件なら最悪 100 万回です。今回は「毎回半分を捨てる」という 1 つの考え方だけで、これを 20 回まで減らします。

100 万件を 1 つずつ見ると、100 万回

順に見ていく方法は、目当ての値が末尾にあると全部を見ることになります。件数が増えれば、そのぶん素直に時間も増えます。

紙の辞書で algorithm を引くとき、1 ページ目から順にめくる人はいません。真ん中あたりを開いて、目的の語がそれより前か後ろかを見て、片側をまるごと無視します。二分探索はこれをそのままコードにしたものです。

半分を捨てると、20 回で終わる

真ん中を 1 か所見るだけで、残りの半分は「見なくてよい」と分かります。これを繰り返すと、候補はこう減っていきます。

1 回の比較で候補が半分になるので、100 万件は 20 回で 1 件まで絞れます。10 億件でも 30 回です。件数が 1000 倍になっても、回数は 10 回しか増えません。これが O(log n) の増え方です。

大事なのは、半分の要素を調べているのではない、というところです。真ん中の 1 件を見ただけで、一度も見ていない残り半分をまとめて候補から外しています。速さの正体はここにあります。

順に見る方法との差は、件数が増えるほど広がります。100 件なら 100 回と 7 回でそれほど困りませんが、100 万件では 100 万回と 20 回です。同じ「探す」でも、比べものにならない差になります。

並んでいないと、半分を捨てられない

半分を捨てられるのは、「真ん中より前には、真ん中以下の値しか無い」と言い切れるからです。この言い切りは、配列が昇順に並んでいることだけを根拠にしています。

この配列で 9 を探すと、真ん中は 1 です。9 は 1 より大きいので右半分に進みますが、9 は左寄りにいるので見つかりません。しかもエラーにはならず、静かに「無い」と答えます。この間違いが厄介なのは、動いてしまうところです。

二分探索を書く前に、その配列が本当に並んでいるかを確かめてください。並んでいないなら、先に並び替えるか、順に見ていく方法を選びます。

候補が空になったら、無い

探す範囲は毎回狭まっていき、いつか 1 件になり、それも違えば 0 件になります。範囲が空になった時点で、配列のどこにも無いと確定します。

範囲をどう持つか、狭めるときに端を 1 つずらすかどうか。ここが二分探索でいちばん間違えやすい部分です。真ん中は違うと分かったのに、その真ん中を次の範囲に残したままにすると、範囲が縮まらず終わらなくなります。

要素が 1 個だけの配列、目当ての値が先頭にある場合、末尾にある場合、そもそも無い場合。この 4 つを紙の上で追ってから書き始めると、書き直しが減ります。特に要素が 1 個の場合は、範囲の持ち方を間違えているとすぐに表面化するので、真っ先に試す価値があります。

1. while ループ (反復) で実装する
2. 計算量は O(log n) になっていること
3. 見つからない場合は -1 を返す