Rubyで探索法（線形・二分・ハッシュ）試してみた．

探索法とは

今回は基本的なお話なので配列で考えます．配列の中にある要素が先頭から何番目にあるのかを確かめようかな？...はい，そこのあなた！そんな時は探索法使いましょうよ！！

とまぁニュアンスはこんな感じですね

#線形探索法(linear_search)
配列の最初の要素から順に中身を確認していきます．みんなしたことあるよね．

linear_search.rb

def linear_search(nums, aim)
  nums.each_with_index do |item, index|
    return index if aim == item
  end
end

nums = [5, 3, 7, 4, 6]
aim = 7
hit = linear_search(nums, aim)
p "nums: #{nums}" # "nums: [5, 3, 7, 4, 6]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 2"

#二分探索法(binary_search)
半分ずつチェックしていきます．注意点は配列の要素が小さい値から大きい値に綺麗に並んでいる必要があることですね．

binary_search.rb

def binary_search(nums, aim)
  nums_head = 0
  nums_tail = nums.size - 1
  while nums_head <= nums_tail
    nums_center = (nums_tail + nums_head) / 2
    case nums[nums_center] <=> aim
    when -1
      nums_head += 1
    when 0
      return nums_center
    else
      nums_tail -= 1
    end
  end
end

nums = [5, 3, 7, 4, 6].sort
aim = 7
hit = binary_search(nums, aim)
p "nums: #{nums}" # "nums: [3, 4, 5, 6, 7]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 4"

#ハッシュ探索法
決められたルールで格納して，そのルールを元に中身を探すんです．これは結構複雑なのでこの記事の最後に載せる本とかで勉強するといいかも．ネットにも色々ありますよ

hash_search.rb

def hash_init(nums)
  hashes = []
  hashes = Array.new(nums.size * 2, 0)
  nums.each do |num|
    k = num % hashes.size
    while_count = 0
    while hashes[k] != 0 || while_count < hashes.size
      k = (k+1) % hashes.size
      while_count += 1
    end
    hashes[k] = num
  end
  hashes
end

def hash_search(nums, aim)
  hashes = hash_init(nums)
  p "hashes: #{hashes}"
  k = aim % hashes.size
  hashes.size.times do
    case hashes[k]
    when 0
      return nil
    when aim
      return k
    else
      k = (k+1) % hashes.size
    end
  end
end

nums = [12, 25, 36, 20, 30, 8, 42]
aim = 36
hit = hash_search(nums, aim)
p "nums: #{nums}" # "nums: [3, 4, 5, 6, 7]"
p "aim: #{aim}, index: #{hit}" # "aim: 7, index: 4"

まとめ

詳しい内容はこの本に載っていますので，オススメですよ！一見，初心者向けのイラスト豊富な内容のない本のように見えますが，中身はしっかりしていました．言語を決めてコードを書いているわけでもないのでどの言語を使う人でも読みやすい一冊でした．
https://www.amazon.co.jp/dp/B01CZDTINE/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1

#おまけ
クラスに入れただけ．

search.rb

class Search
  def initialize(nums, aim)
    @nums = nums
    @aim = aim
  end
  def linear_search
    @nums.each_with_index do |item, index|
      return index if @aim == item
    end
  end
  
  def binary_search
    nums_head = 0
    nums_tail = @nums.size - 1
    while nums_head <= nums_tail
      nums_center = (nums_tail + nums_head) / 2
      case nums[nums_center] <=> @aim
      when -1
        nums_head += 1
      when 0
        return nums_center
      else
        nums_tail -= 1
      end
    end
  end
  
  def hash_init(nums)
    hashes = []
    hashes = Array.new(nums.size * 2, 0)
    nums.each do |num|
      k = num % hashes.size
      while_count = 0
      while hashes[k] != 0 || while_count < hashes.size
        k = (k+1) % hashes.size
        while_count += 1
      end
      hashes[k] = num
    end
    hashes
  end

  def hash_search
    hashes = hash_init(@nums)
    p "hashes: #{hashes}"
    k = @aim % hashes.size
    hashes.size.times do
      case hashes[k]
      when 0
        return nil
      when @aim
        return k
      else
        k = (k+1) % hashes.size
      end
    end
  end
end

p nums = [12, 25, 36, 20, 30, 8, 42]
aim = 36
search = Search.new(nums, aim)
hit = search.hash_search
p "aim: #{aim}, hit: #{hit}"

#追記(2018/11/08)
コメントでご指摘いただいた内容<@scivola 様>で，僕が知らなかった便利なメソッド等がありましたのでこちらに記載させていただきます．

• whileはnilを返す...メソッドの返り値はそのメソッド内での最後の処理なのですが，繰り返しがその最後の処理の場合はnilを返してくれるらしいです．
• Array.new(num, 0)...配列を作る際に，あらかじめ決まった要素数(num)に全て0を入れたいなぁって場合はこの一行で作れるようです．繰り返しを用いるよりコードが軽くなるので積極的に使っていきたいですね．
• Numeric#<=>...2つの値の関係を-1, 0, 1, nilで表してくれる優れもの．