第34回 Ruby/Rails 勉強会 - 演習 3

演習問題のつづき。

バイナリサーチを再帰で実装してください。

class Array
  def bsearch(o, n = 0)
    return nil  if empty?

    i = size/2
    if self[i] == o
      i+n
    elsif self[i] > o
      self[0,i].bsearch(o, n)
    else
      self[i+1,i].bsearch(o, n+i+1)
    end
  end
end

a = (0..9).to_a             # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
(0..9).each do |i|
  a.bsearch i               # => 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
end

even = a.select{|i|i%2==0}  # => [0, 2, 4, 6, 8]
(0..9).each do |i|
  even.bsearch i            # => 0, nil, 1, nil, 2, nil, 3, nil, 4, nil
end

odd = a.reject{|i|i%2==0}   # => [1, 3, 5, 7, 9]
(0..9).each do |i|
  odd.bsearch i             # => nil, 0, nil, 1, nil, 2, nil, 3, nil, 4
end

String#[](start, length) って始めて使った気がする。