アルゴリズムのキホン

アルゴリズムのキホン

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

第5章 並べ替えと探索

• 線形探索（リニアサーチ）

def liner_search(base, target)
  base.each_with_index do |v, idx|
    return idx if v == target
  end

  nil
end

base = [2, 9, 5, 1, 7, 8, 3, 4]
puts liner_search(base, 7)
puts liner_search(base, 6)

• 二分探索（バイナリサーチ）
  ごちゃごちゃしすぎ？全然すっきりしてないなぁ。

base = [2, 5, 6, 9, 12, 15, 16, 19, 24, 27, 30]

target = 20
start = 0
result = nil
nth = base.count / 2
work = nth / 2

loop do
  puts "start : %s, base[nth] : %s, nth : %s" % [start, base[nth], nth]
  if base[nth] == target
    result = nth
    break
  end

  break if work == 0

  if base[nth] > target
    nth = start + work
  else
    start = nth
    nth += work
  end

  work /= 2
  puts "nth : %s, work : %s" % [nth, work]
end

puts "result: %s" % result