【Ruby】二分探索, lower_bound, upper_bound

　Ruby2.3 以降には見つけた値のインデクスを返す Array.bsearch_index() があるのだが、自作した方が使い勝手が良いことも多いので、Java 版をそのまま移植してみた。

■組み込み関数
■オープンクラス版
■二分探索でソート済み配列を作る
■二分探索で検索する値の個数を求める
■通常のメソッド版

なお、組み込み関数の場合は以下のようになる。

●Ruby の bsearch_index で lower_bound, upper_bound 的な動作 (Ruby 2.3以降)

     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;
lower = arr.bsearch_index{|x| x >= v}  #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
upper = arr.bsearch_index{|x| x > v}   #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
print "lower = #{lower}\n"
print "upper = #{upper}\n"

lower = 2
upper = 5

　値の意味は lower_bound 的な方は「指定した値以上の先頭の要素を返す」ことになるので、配列 arr 内で v = 3 が続く値の先頭インデクス = 2 を、upper_bound 的な方は「指定した値より大きい先頭の要素を返す」ことになるので、v = 3 が続く値より後ろのインデクス = 5 という意味になる。

　ちなみに Array.bsearch() の方は要素の値そのものを返す。今回の関数と組み込み関数との大きな違いは、値が見つからないとき nil (組み込み関数)か、近いインデクスを返す(今回の関数)かという感じだ。実は見つからないとき値を返すようにしておくと、色々利用できるのでわざわざ Java から（元はC++） 移植したわけだ。

●二分探索：binary_search, lower_bound, upper_bound (オープンクラス版)

#オープンクラス版
class Array
  #二分探索(同値連続はインデクス不定となる)
  #見つからないとき=負の値となり、~index で挿入位置になる
  def binary_search(value, from = 0, to = self.size)
    low = from
    high = to - 1
    while low <= high
      mid = (low + high) / 2
      if self[mid] < value
        low = mid + 1
      elsif self[mid] > value
        high = mid - 1
      else
        return mid
      end
    end
    -(low + 1) #見つからない(~index で挿入位置)
  end

  #指定した値以上の先頭のインデクスを返す
  def lower_bound(value, from = 0, to = self.size)
    low = from
    high = to
    while low < high
      mid = (low + high) / 2
      if self[mid] < value
        low = mid + 1
      else
        high = mid
      end
    end
    low
  end

  #指定した値より大きい先頭のインデクスを返す
  def upper_bound(value, from = 0, to = self.size)
    low = from
    high = to
    while low < high
      mid = (low + high) / 2
      if self[mid] <= value
        low = mid + 1
      else
        high = mid
      end
    end
    low
  end

end


#メインでは...
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;    #検索する値
print "binary_search = #{arr.binary_search(v)}\n"
print "lower_bound = #{arr.lower_bound(v)}\n"
print "upper_bound = #{arr.upper_bound(v)}\n"

print "bsearch_index(lower) = #{arr.bsearch_index{|x| x >= v}}\n"  #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3)
print "bsearch_index(upper) = #{arr.bsearch_index{|x| x > v}}\n"  #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3)

binary_search = 3
lower_bound = 2
upper_bound = 5
bsearch_index(lower) = 2
bsearch_index(upper) = 5

　意味は組み込み関数の例とだいたい同じになる。違いは値が見つからないときの戻値だ。例えば検索する値を v = 2 とすると、組み込み関数の場合 nil となるが、lower_bound()、upper_bound() は 2 となる。binary_search() の場合は -3 という値が返るが、この値はビット反転すると（~index = ~(-3)）2 となる。つまり、binary_search() の場合、同値が連続しているとき、どのインデクスになるかは不定だが、負の値が返ってきたとき見つからなかったことがわかるので、処理分岐がしやすい利点がある。

　また、Ruby には関数のオーバーロードがないので、検索範囲を決める引数（from = 開始インデクス、to = 終了インデクス[このインデクスは含まない] はデフォルト値を設定してある（デフォは配列の最初から最後まで）。検索するインデクス範囲がわかっているなら、絞り込めば更に高速に動作する。余談だが、範囲を決める引数を関数に持たせる場合、終了インデクスは「含まない」としておくと、差分計算や連続検索などしやすくなる（標準ライブラリ等もだいたいそうなっている）。

　あと lower_bound() も upper_bound() も要素の最大より上の値を検索すれば、配列の長さと同じ値が返ってくる（例えば、v = 9 とすれば、どちらもインデクス = 15 が返る）。これらは値が見つからないとき、配列の最後に値を追加するのに使える。この方法を使えば、リアルタイムにソート済み配列を作ることも可能だ。試しにやってみよう。

●二分探索でソート済み配列を作る

arr = [3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
sorted = []

arr.each{|e|
  sorted.insert(sorted.upper_bound(e), e)

#  sorted.insert(sorted.lower_bound(e), e)

#  idx = sorted.binary_search(e)
#  if idx < 0
#    idx = ~idx
#  end
#  sorted.insert(idx, e)
}

p arr
p sorted

[3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

　この場合は binary_search(), lower_bound(), upper_bound() どれを使っても同じになる。しかし実際には同値がある場合、binary_search() は同値の中ではそのどこかに、lower_bound() の場合は同値の先頭に、upper_bound() の場合は同値の一番最後（＝検索値の次の値の先頭）に挿入されることになる。追加順序が必要な場合は使い分けた方が良いだろう。もちろんこの例の場合は最後にソート（Array.sort()）でも良いが、リアルタイムに追加・削除を繰り返す場合は、何度もソートするより負荷が軽くなる。

　もう１つ、lower_bound() と upper_bound() を上手く使う例として、指定範囲内の値の個数を求めてみよう。

●lower_bound() と upper_bound() で検索範囲内の値の個数を求める

arr = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]

lo, hi = 1, 3   #検索する値の範囲
fr = arr.lower_bound(lo)  #開始インデクスを表す
to = arr.upper_bound(hi)  #終了インデクスを表す[このインデクスは含まない]

p arr
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"  #差分が個数
p arr.slice(fr, to - fr)  #範囲を抜き出し

[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]
fr = 3, to = 17, cnt = 14
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]

　この例は配列の中から、検索する値 = 1～3 のインデクス範囲（3～17 [17は含まない]）を取得し、差分から個数を求めている。Array.slice() はおまけでその範囲を抜き出して表示しているだけだ。もちろんこのくらいの数なら逐次検索でもそれほど差がないかも知れないが、要素数が多くなると効果はてきめんとなる。

　最後にオープンクラスで使いたくない人のためにも通常のメソッドでも書いておこう。内容は全く同じになるので、好きな方を使えば良い。

●二分探索：binary_search, lower_bound, upper_bound (通常メソッド版)

#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(arr, value, from = 0, to = arr.size)
  low = from
  high = to - 1
  while low <= high
    mid = (low + high) / 2
    if arr[mid] < value
      low = mid + 1
    elsif arr[mid] > value
      high = mid - 1
    else
      return mid
    end
  end
  -(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(arr, value, from = 0, to = arr.size)
  low = from
  high = to
  while low < high
    mid = (low + high) / 2
    if arr[mid] < value
      low = mid + 1
    else
      high = mid
    end
  end
  low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(arr, value, from = 0, to = arr.size)
  low = from
  high = to
  while low < high
    mid = (low + high) / 2
    if arr[mid] <= value
      low = mid + 1
    else
      high = mid
    end
  end
  low
end


#メインでは...
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;    #検索する値

print "binary_search = #{binary_search(arr, v)}\n"
print "lower_bound = #{lower_bound(arr, v)}\n"
print "upper_bound = #{upper_bound(arr, v)}\n"

s, e = 3, 6    #検索する値の範囲
fr = lower_bound(arr, s)
to = upper_bound(arr, e)
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"

binary_search = 3
lower_bound = 2
upper_bound = 5
fr = 2, to = 12, cnt = 10

　オンラインジャッジの問題でも上級レベルになるほど、逐次検索では計算量が間に合わずタイムアウトしやすくなる。CodeIQ でも paiza でもランク A, S（★★★★）問題には必要となるシーンも多いので、使える場合は積極的に使ってみると良いだろう（要するに単純な昇順・降順データ・累積和・フィボナッチのような増加数列には使った方が安全）。標準ライブラリにあるものでも、その実装に近いものを知っていれば柔軟に対応できるようになるので、色々改造して使うと良いだろう。


（関連記事）
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする

■参考になる書籍