Rubyで二分探索する

配列に含まれる要素を検索する際に、対象の配列がソート済みの場合は二分探索（バイナリサーチ）を用いると高速に検索できます。

Rubyには配列の二分探索を行うメソッドとして`Array#bsearch`、`Array#bsearch_index`が用意されているので、わざわざ自前で二分探索を実装する必要がありません。

今回はこの二分探索の使い方とベンチマーク比較を紹介します。

## `Array#bsearch`の使い方

はじめに`Array#bsearch`についてです。
このメソッドはブロックの評価結果で条件を満たす値を二分探索で検索しその値を返します。

https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch.html

以下はソートされた配列から4より大きい数字を取得する例です。

```ruby
ary = [1, 3, 5, 7, 11]
puts ary.bsearch{|a| a > 4}
# 5が出力される
```

## `Array#bsearch_index`の使い方

次は`Array#bsearch_index`についてです。
このメソッドはブロックの評価結果で条件を満たす値を二分探索で検索しその位置を返します。

https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch_index.html

以下はソートされた配列から4より大きい数字の位置を取得する例です。先頭の位置が0番目なので5の位置は2となります。

```ruby
ary = [1, 3, 5, 7, 11]
puts ary.bsearch_index{|a| a > 4}
# 2が出力される
```

## 二分探索以外との方法との性能比較

### 前提となる環境

```
ruby 3.2.0 (2022-12-25 revision a528908271) [arm64-darwin22]
```

### `Array#include?`と比較

まずはじめに配列に要素が存在するかを判定する`Array#include?`と比較してみます。

配列の要素数が100,1000,10000,100000の場合でそれぞれ1万回処理したときのベンチマークを取ります。


```ruby
require 'benchmark'

n = 10000
data_size = [100, 1000, 10000, 100000]

Benchmark.bm do |x|
  data_size.each do |d|
    ary = (0..d-1).to_a

    puts "要素数:#{d}"
    x.report 'Array#include?' do
      n.times do
        target = rand(d)
        ary.include?(target)
      end
    end

    x.report 'Array#bsearch' do
      n.times do
        target = rand(d)
        ary.bsearch{|a| a == target}
      end
    end
  end
end
```

結果は以下の通りです。

```
       user     system      total        real
要素数:100
Array#include?  0.002923   0.000002   0.002925 (  0.002923)
Array#bsearch  0.002766   0.000000   0.002766 (  0.002766)
要素数:1000
Array#include?  0.018837   0.000003   0.018840 (  0.018840)
Array#bsearch  0.003403   0.000001   0.003404 (  0.003402)
要素数:10000
Array#include?  0.173394   0.000026   0.173420 (  0.173415)
Array#bsearch  0.004416   0.000001   0.004417 (  0.004416)
要素数:100000
Array#include?  1.720558   0.000408   1.720966 (  1.720927)
Array#bsearch  0.005206   0.000008   0.005214 (  0.005231)
```

いずれの結果も`Array#bsearch`の方が速くなりました。
`Array#include?`の計算量がO(n)に対して`Array#bsearch`の計算量はO(log n)なので、要素数が増えるにつれて差が大きく開いていくことがわかります。

### その他様々なメソッドと比較

次は似たようなメソッドの`Array#find`、`Array#bsearch_index`、`Set#include?`、`Set#find`とも比較してみました。

```ruby
require 'benchmark'

n = 10000
data_size = [100, 1000, 10000, 100000]

Benchmark.bm do |x|
  data_size.each do |d|
    ary = (0..d-1).to_a
    s = Set.new(ary)

    puts "要素数:#{d}"
    x.report 'Array#include?' do
      n.times do
        target = rand(d)
        ary.include?(target)
      end
    end

    x.report 'Array#find' do
      n.times do
        target = rand(d)
        ary.find{|a| a == target}
      end
    end

    x.report 'Array#bsearch' do
      n.times do
        target = rand(d)
        ary.bsearch{|a| a == target}
      end
    end

    x.report 'Array#bsearch_index' do
      n.times do
        target = rand(d)
        ary.bsearch_index{|a| a == target}
      end
    end

    x.report 'Set#include?' do
      n.times do
        target = rand(d)
        s.include?(target)
      end
    end

    x.report 'Set#find' do
      n.times do
        target = rand(d)
        s.find{|b| b == target}
      end
    end
  end
end
```

実行した結果は以下の通りです。

```
       user     system      total        real
要素数:100
Array#include?  0.002954   0.000000   0.002954 (  0.002950)
Array#find  0.019293   0.000123   0.019416 (  0.019418)
Array#bsearch  0.002672   0.000013   0.002685 (  0.002685)
Array#bsearch_index  0.002650   0.000044   0.002694 (  0.002697)
Set#include?  0.001320   0.000005   0.001325 (  0.001324)
Set#find  0.020483   0.000095   0.020578 (  0.020579)
要素数:1000
Array#include?  0.018342   0.000066   0.018408 (  0.018406)
Array#find  0.158500   0.000600   0.159100 (  0.159104)
Array#bsearch  0.003366   0.000004   0.003370 (  0.003373)
Array#bsearch_index  0.003339   0.000000   0.003339 (  0.003340)
Set#include?  0.001353   0.000000   0.001353 (  0.001353)
Set#find  0.172065   0.001208   0.173273 (  0.173275)
要素数:10000
Array#include?  0.170974   0.000680   0.171654 (  0.171660)
Array#find  1.535577   0.009384   1.544961 (  1.544990)
Array#bsearch  0.004513   0.000054   0.004567 (  0.004642)
Array#bsearch_index  0.004381   0.000000   0.004381 (  0.004384)
Set#include?  0.001445   0.000009   0.001454 (  0.001453)
Set#find  1.683042   0.008779   1.691821 (  1.691840)
要素数:100000
Array#include?  1.714387   0.007768   1.722155 (  1.722186)
Array#find 15.526816   0.069367  15.596183 ( 15.596378)
Array#bsearch  0.005219   0.000037   0.005256 (  0.005366)
Array#bsearch_index  0.005073   0.000009   0.005082 (  0.005084)
Set#include?  0.002169   0.000001   0.002170 (  0.002171)
Set#find 16.573293   0.083549  16.656842 ( 16.656929)
```

`Array#bsearch`と`Array#bsearch_index`に速度の違いはほとんどないことがわかります。
`Array`も`Set`も要素を値指定で検索する際は`find`ではなく`include?`を使う方が速くなりました。また、`Array#find`と`Set#find`では若干`Array#find`の方が早いようです。

そして結局は集合を扱う`Set`を使った`Set#include?`が二分探索と比較しても一番高速でした。

### まとめ

ソートされた配列を検索する際は`Array#bsearch`や`Array#bsearch_index`で二分探索を行うと速く検索できることがわかりました。また、要素数が増えるにつれて二分探索と線形探索との性能差は大きくなるので、大量データを検索する時は非常に二分探索が効果的です。

ただし、すでに存在する配列に対して一度ソートを行ってから二分探索を行ってしまうとソート処理の分かえって速度が遅くなってしまうことがあるので注意が必要です。あくまで事前にソートされているデータで利用しましょう。


その他にも集合`Set`を使用することで要素の存在チェックを高速に行うことができます。
こちらもすでに配列で保持しているデータをSetに変換するとその分のコストが掛かり逆に遅くなってしまうので注意が必要です。