二分探索 (O(log n))
100 万件を、20 回で当てる
前回の線形探索は、100 万件なら最悪 100 万回比べます。ところが配列が小さい順に並んでいるだけで、同じ探索が 20 回 で終わります。回数を 5 万分の 1 にする仕掛けが二分探索です。
種明かしは、1 から 100 までの数を当てるゲームと同じです。「50 より大きいですか」と聞けば、答えが「はい」でも「いいえ」でも候補は半分消えます。次は 25 か 75 を聞く。1 から順に「1 ですか」「2 ですか」と聞く人はいません。
半分に割るたび、候補はこう減る
候補が 100 件だったとして、真ん中を 1 回見るたびに残る件数は次のように減ります。
| 見た回数 | 残る候補 |
|---|---|
| 0 回 | 100 |
| 1 回 | 50 |
| 2 回 | 25 |
| 3 回 | 13 |
| 4 回 | 7 |
| 5 回 | 4 |
| 6 回 | 2 |
| 7 回 | 1 |
7 回で 1 件まで絞れました。これが log2(100) がおよそ 7 だ、という意味です。件数が 100 万でも、同じ数え方で 20 回です。
Python
n = 1000000
steps = 0
while n > 1:
n //= 2
steps += 1
print(steps) # 20件数を 1000 倍にしても、回数は 10 増えるだけです。O(log n) はこういう増え方をします。
並んでいないと、半分を捨てられない
この速さは「真ん中より大きいのだから、左半分には絶対に無い」という判断に丸ごと乗っています。並んでいない配列で同じ判断をすると、平気で存在する値を見落とします。使う前に、その配列が昇順に並んでいるかを必ず確かめてください。
真ん中の位置を出すときは、整数の割り算を使います。
Python
print(7 / 2) # 3.5
print(7 // 2) # 33.5 番目という位置は存在しないので、小数のままではインデックスに使えません。JavaScript には整数の割り算が無いので、切り捨てを自分で書きます。
JavaScript
console.log(Math.floor(7 / 2)); // 3範囲が縮まないと、いつまでも終わらない
二分探索でいちばん多い事故は、答えを間違えることではなく 終わらない ことです。真ん中を見て候補を絞ったつもりが、範囲の端が 1 つも動いていない、という書き方をすると、同じ場所を永遠に見続けます。1 周まわるごとに範囲が確実に狭くなっているか、手を止めて確かめてください。
もう 1 つは、候補が 1 件だけ残った状態を見ずに終わってしまうことです。1 件残っているなら、それはまだ調べていない 1 件です。[42] のような 1 件だけの配列を渡してみると、この取りこぼしにすぐ気づけます。
要件
- 二分探索 (左右の境界を毎回半分に縮める) で実装すること
- 見つかった場合はそのインデックスを、見つからない場合は -1 を返す
- 配列は昇順ソート済みであることを前提として良い
入出力例
binarySearch([1,3,5,7,9,11,13], 9) → 4
binarySearch([1,3,5,7,9], 1) → 0
binarySearch([1,3,5,7,9], 9) → 4
binarySearch([1,3,5,7,9], 6) → -1
binarySearch([42], 42) → 0
binarySearch([42], 7) → -1
binarySearch([2,4,6,8,10,12,14,16,18,20], 14) → 6ヒント
