ヽ｜∵｜ゝ(Fantom) の 開発blog？

     #[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"

#オープンクラス版
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)

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

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)  #範囲を抜き出し

#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~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"

#階乗・順列・組合せの個数(オープンクラス)
class Integer
  def factorial
    return 1 if self == 0
    (1..self).inject(:*)
  end

  def permutation(r)
    return 1 if self == 0
    s = self - r + 1
    (s..self).inject(:*)
  end

  def combination(r)
    r = [r, self - r].min
    return self if r == 1
    return 1 if r == 0
    self.permutation(r) / r.factorial
  end
end


#メインでは...
n = 6
r = 3
print "#{n}!  = #{n.factorial}\n"
print "#{n}P#{r} = #{n.permutation(r)}\n"
print "#{n}C#{r} = #{n.combination(r)}\n"

#階乗・順列・組合せの個数(通常のメソッド)
def factorial(n)
  return 1 if n == 0
  (1..n).inject(:*)
end

def permutation(n, r)
  return 1 if n == 0
  s = n - r + 1
  (s..n).inject(:*)
end

def combination(n, r)
  r = [r, n - r].min
  return n if r == 1
  return 1 if r == 0
  permutation(n, r) / factorial(r)
end


#メインでは...
n = 6
r = 3
print "#{n}!  = #{factorial(n)}\n"
print "#{n}P#{r} = #{permutation(n, r)}\n"
print "#{n}C#{r} = #{combination(n, r)}\n"