二分探索 (反復版)

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

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

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

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

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

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

1000000 -> 500000 -> 250000 -> 125000 -> ... -> 2 -> 1

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

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

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

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

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

arr = [3, 7, 1, 9, 4]     # 並んでいない

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

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

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

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

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

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

演習で使う書き方

例は価格 [20, 40, 60, 80, 100] から 80 を探す場面です。中央の 60 は小さいので右の [80, 100] だけを残し、次の中央で見つかります。// は整数の割り算、while は条件が成立する間の繰り返しです。演習では中央の計算、比較、両端の更新を書きます。

1. 中央の比較と探索範囲の更新を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える