Ruby 配列における find と bsearch の違い（ブロックの書き方に注意）
配列の中から特定の値を探す時に find メソッドを使うことができますが、配列がソートされている場合には、 bsearch メソッドを使うことでより高速に探索することができます。ここでは、それぞれの特徴と使い方を比較します。
find（線形探索）とは
先頭から順に比較して値を探す方法です。
メリット：ソートされていない配列を探索できる
デメリット：最悪のケースでは、配列の最後の要素まで確認する必要があるため時間がかかる
find の使い方
array = [7, 15, 0, 4, 12, 19, 10]
array.find { |x| x == 12 } #=> 12
bsearch（二分探索）とは
ソート済み配列の中央の値を見て、探索したい値が中央より右側・左側のどちらにあるかを判断することで、候補を絞りながら探す方法です。
メリット：配列の要素数が多い場合でも、高速に探索することができる
デメリット：配列がソートされていないと使うことができない
bsearch の使い方（誤）
sorted_array = [0, 4, 7, 10, 12, 15, 19]
sorted_array.bsearch { |x| x == 12 } #=> nil
これで find と同じように 12 を探し出して…いません！find と同様にブロックを渡しましたが、これでは意図した通り動かないようです。
bsearch の使い方（正）
落ち着いてリファレンスを参照してみます。
find-minimum モード(特に理由がない限りはこのモードを使う方がいいでしょ う)では、条件判定の結果を以下のようにする必要があります。
求める値がブロックパラメータの値か前の要素の場合: true を返す
求める値がブロックパラメータより後の要素の場合: false を返す
🤔🤔🤔🤔🤔
つまりどういうことか図解すると…
このように、求める値とそれより右側が全て true になるようにブロックを渡してあげると、1番左側の 12 を探し出してくれます！
これを踏まえて、正しいコードがこちらです。
sorted_array = [0, 4, 7, 10, 12, 15, 19]
sorted_array.bsearch { |x| x >= 12 } #=> 12
配列が降順にソートされている時
sorted_array = [19, 15, 12, 10, 7, 4, 0]
sorted_array.bsearch { |x| x <= 12 } #=> 12
降順でも使えます！
昇順の時と同様、求める値である 12 以後が true になれば良いので、比較演算子を逆向きにしています。
bsearch の使いどころ
- 元から配列がソートされている
- 配列はソートされていないが、何度も探索する必要があるため、前準備としてソートしてしまった方が良い
上記のような状況で効果的です。
備考
AtCoderで bsearch を使うドンピシャの問題（Ruby実装例）があって感激しつつも、思い通りに動く時と動かない時があり少しハマったので、リファレンスを調べて記事にまとめてみました。ソート済みの配列には bsearch ！
参考一覧
module Enumerable (Ruby 2.6.0)
instance method Array#bsearch (Ruby 2.6.0)
instance method Array#bsearch_index (Ruby 2.6.0)
添字を取得したい時は bsearch_index が使えます。
