2014年1月17日金曜日

RubyのArray#bsearch,Range#bsearchの使い方とサンプルコード

ソート済み配列に対してバイナリサーチを行うArray#bsearch, Range#bsearchの使い方について、ありがちな状況ごとにまとめてみた。

ある値が配列に含まれているか調べる

Array#bsearchでfind-anyモードを使用する。find-anyモードのブロックではstrcmpmemcmpの返り値と同じように、探している値がブロックに渡された値よりも大きければ正、等しければ0、小さければ負の整数を返す。メソッドの返り値は探している値と等しい要素か、見つからない場合はnil

ary = [1, 3, 3, 5]
p ary.bsearch {|x| 3 <=> x } != nil # => true
p ary.bsearch {|x| 2 <=> x } != nil # => false

インデックスが必要な場合はRange#bsearchを使う。

p (0...ary.size).bsearch {|i| 3 <=> ary[i] } # => 1
p (0...ary.size).bsearch {|i| 2 <=> ary[i] } # => nil

配列内の境界(boundary)について調べる

Range#bsearchでfind-minimumモードを使用する。find-minimumモードのブロックでは、探している値がブロックに渡された値と等しいか小さい場合はtrue、大きい場合はfalseを返す。メソッドの返り値はブロック内の条件を満たす最小の要素。

lower boundaryを探す。この場合は先頭の3

ary = [1, 3, 3, 5]
p (0...ary.size).bsearch {|i| ary[i] >= 3 } # => 1

upper boundaryを探す。この場合は末尾の3。ひとつ先のインデックスが返ることに注意。

p (0...ary.size).bsearch {|i| ary[i] > 3 } # => 3

等しい要素が存在しない場合は次に大きい要素(条件を満たす最小の要素)のインデックスが返る。

p (0...ary.size).bsearch {|i| ary[i] >= 2 } # => 1
p (0...ary.size).bsearch {|i| ary[i] > 2 }  # => 1

条件を満たす要素が存在しない場合はnil

p (0...ary.size).bsearch {|i| ary[i] >= 6 } # => nil
p (0...ary.size).bsearch {|i| ary[i] > 6 }  # => nil

ということで、Rangeで欲しい場合は次のようにする。

size = ary.size
lower = (0...size).bsearch {|i| ary[i] >= 3 } || size
upper = (lower...size).bsearch {|i| ary[i] > 3 } || size
p lower...upper # => 1...3

ただし、見つからない場合は始端と終端が等しくなるので、

lower == upper ? nil : lower...upper

とした方がいい場合もあるかもしれない。

ソート済み配列に挿入する

Range#bsearchでインデックスを求めてから、Array#insertを呼ぶ。 Array#insertは、第1引数で与えられたインデックスの要素の直前に、第2引数以降で与えられた要素を挿入するメソッド。

条件を満たす要素が存在しない場合はnilが返るので|| ary.sizeが必要。

ary = [1, 3, 3, 5]
i = (0...ary.size).bsearch {|i| ary[i] >= 6 } || ary.size
p ary.insert(i, 6) # => [1, 3, 3, 5, 6]

重複要素の先頭に挿入する。

ary = [1, 3, 3, 5]
i = (0...ary.size).bsearch {|i| ary[i] >= 3.0 } || ary.size
p ary.insert(i, 3.0) # => [1, 3.0, 3, 3, 5, 6]

重複要素の末尾に挿入する。

ary = [1, 3, 3, 5]
i = (0...ary.size).bsearch {|i| ary[i] > 3.0 } || ary.size
p ary.insert(i, 3.0) # => [1, 3, 3, 3.0, 5, 6]