array_bsearch.md

Array#bsearch の前提について

arrayはソート済みである必要がある。ここで言う「ソート済み」とは、各要素に対してブロックを評価した場合に

[false, false, false, false, true, true]

みたいな感じになっている必要がある、という意味で、

[true, false, true, false, true]

みたいなバラバラとか

[true, true, false, false, false, false]

みたい逆順のソートとかではだめですよ、ということである。

データがソート済みであるとき、 true になる要素のうち一番前のものを、下のような手順で探しますよ、というのが Array#bsearch である

動きの例

たとえば [15, 14, 13, 12, 11, 10, 9, 8, 7 , 6, 5, 4, 3, 2, 1].bsearch { |e| e < 3 } の場合

1. 真ん中のものとして 8 を選ぶ
2. 8 < 3 は false なので、より後ろのものを見る
3. [7, 6, 5, 4, 3, 2, 1] が残る
4. 真ん中の 4 を選ぶ
5. 4 < 3 は false なので、より後ろのものを見る
6. [3, 2, 1]が残る
7. 真ん中のものとして 2 を選ぶ
8. 2 < 3 は true なので 2 か、それよりも前に探しているものがある。
9. [3,2]のうち真ん中のものとして 3 を選ぶ
10. 3 < 3 は偽なので、3より後ろに探しているものがある
11. 2 が最終的に見つかるので 2を返す

こうやって、真ん中の要素をチェックして、お目当てのものがそれより後ろにあるか前にあるかを調べる、という手順を繰り返すことで、お目当ての要素を探すのがbsearch(バイナリサーチ)である。

もう少し bsearch について

例えば score というメソッドを持っている User クラスのオブジェクトの配列([user_a, user_b, user_c, user_d ...])があったとする。しかもこのとき、User#score はけっこう重い処理だったりするとしよう。このとき、全件検査したり前から全部検査していくと結構辛い感じになる。でも、バイナリサーチをすることで、User#score を呼び出す回数が減る可能性が非常に高くなる。 User#score がたとえば結構重い処理だったりするなら、これはかなりうれしみがある。