Ruby で二分探索(バイナリサーチ)

Ruby で二分探索(バイナリサーチ)やるなら bsearch が使える。

Array#bsearch (Ruby 3.1 リファレンスマニュアル)

ブロックの評価結果で範囲内の各要素の判定を行い、条件を満たす値を二分探索(計算量は O(log n))で検索します。要素が見つからない場合は nil を返します。self はあらかじめソートしておく必要があります。

ary = [0, 4, 7, 10, 12]
ary.bsearch {|x| x >=   4 } # => 4
ary.bsearch {|x| x >=   6 } # => 7
ary.bsearch {|x| x >=  -1 } # => 0
ary.bsearch {|x| x >= 100 } # => nil

あと二分探索はあまりにも有名なアルゴリズムなので自分でもささっとアルゴリズムを書けるようになっておきたい。