[Ruby]二分探索を行うbsearch, bsearch_indexについて学ぶ

はじめに

最近、bsearch_indexという未知のメソッドの存在をchatGPT経由で知り、調べてみるとSQLのインデックスにも使用される二分探索を行うメソッドであることを知りました。
そもそも二分探索ってなんだ？という状態だったので、併せて記事にして勉強してしまおう〜という経緯で本記事を作成するに至りました。

二分探索とは

二分探索（バイナリサーチ）は、ソートされた配列内から特定の要素を効率的に見つけ出すための探索アルゴリズムです。
通常の線形探索では、配列のすべての要素を一つずつ確認していきますが、二分探索では配列を中央で分割し、目的の値が中央より小さいか大きいかで探索範囲を半分に絞っていきます。
このように半分ずつ選択肢を消去していくことで計算量が O(log n) となり、大規模なデータセットでも高速に処理できます。

注意すべきことは、対象の配列が ソートされていることを前提としていることです。

たとえば、次のようなソートされていない配列があるとします。

array = [8, 3, 5, 1, 9, 6]

ここで、「5」を探すために二分探索を試みるとします。二分探索ではまず配列の真ん中の要素と比較しますが、順序が整っていないためどちらの方向に探索を進めるべきか分からなくなってしまいます。

配列の中央の要素である「1」と「5」を比較します。
二分探索では、「5」は「1」より大きいので右側を探索するべき、と判断しますが、ソートされていないため、右側に「5」があるとは限りません。
実際、右側の範囲 [9, 6] には「5」が含まれていません。
左側の [8, 3, 5] に「5」があるのですが、二分探索ではこれを無視してしまう可能性があります。
このように、ソートされていない配列では、「特定の方向に要素が存在する」という前提が崩れるため、効率的な探索ができなくなるのです。これは納得ですね。

二分探索については、以下のサイトが非常にわかりやすかったです。

bsearch, bsearch_indexについて

Rubyには、この二分探索アルゴリズムを簡単に利用できるbsearchとbsearch_indexというメソッドが用意されています。これらのメソッドをそれぞれ見ていきましょう。

bseach

bsearch は、ブロック内の条件に一致する最初の要素を返すメソッドです。要素が見つからない場合は nil を返します。

以下のように使用できます。

array = [1, 3, 5, 7, 9, 11]

# 5以上の最初の要素を探す
result = array.bsearch { |x| x >= 5 }
puts result  # => 5

このように、「ある範囲以上の数値の中で最小のものを探す」といったケースでは有効に機能しそうです。
「本当にパフォーマンス向上するのか？？」と思ったのでRubyのfindメソッドとパフォーマンスを比較してみましょう。

require 'benchmark'

# ランダムに並べられた数値10,000個の配列を生成
random_array = Array.new(10_000) { rand(1000) }.sort  # bsearchに対応するためソート

# 検索条件：500以上の最初の要素を見つける
target_value = 500

Benchmark.bm do |x|
  x.report("bsearch") do
    random_array.bsearch { |x| x >= target_value }
  end

  x.report("find") do
    random_array.find { |x| x >= target_value }
  end
end

これをwebコンソールで試してみると、、、bsearchの方がかなりフォーマンス面において優れていることがわかります。その差なんと72倍。これは確かに然るべき場面で選択肢に入れたいですね。

         user       system     total      real
bsearch  0.000007   0.000001   0.000008   (0.000004)
find     0.000288   0.000000   0.000288   (0.000288)

bseach_index

bsearch_indexは、特定の条件を満たす要素の「インデックス」を返すメソッドです。
スケジュールされたイベントリストから、特定の日付以降の最初のイベントを見つけたい場合など、配列のインデックスが必要な場合に便利です。

以下のように使用できます。

array = [1, 3, 5, 7, 9, 11]

# 5以上の最初の要素のインデックスを探す
index = array.bsearch_index { |x| x >= 5 }
puts index  # => 2

こちらに関しても、Rubyのfind_indexとパフォーマンスを比較してみましょう。

require 'benchmark'

# ソートされた10,000個の数値が入った配列
sorted_array = Array.new(10_000) { |i| i }

# 検索条件：5000以上の最初の要素のインデックスを見つける
target_value = 5000

Benchmark.bm do |x|
  x.report("bsearch_index") do
    sorted_array.bsearch_index { |x| x >= target_value }
  end

  x.report("find_index") do
    sorted_array.find_index { |x| x >= target_value }
  end
end

こちらもbsearch_indexの方がかなり処理速度が速いですね。

               user      system    total     real
bsearch_index  0.000006  0.000002  0.000008  (0.000004)
find_index     0.000140  0.000054  0.000194  (0.000194)

まとめ

最後までお読みいただきありがとうございます。
探索方法の工夫でこんなにパフォーマンスが変わるとは。。かなり驚きました。
ソートされた配列を扱う時には、これらのメソッドも選択肢に入れて考えようと思いました。
また、SQLのインデックスにもこの仕組みが導入されているそうなので、そちらに関しても深掘って勉強しようと思います。