アルゴリズムのキホン
アルゴリズムのキホン
「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)
- 作者: 杉浦賢
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/18
- メディア: 単行本
- 購入: 3人 クリック: 32回
- この商品を含むブログ (15件) を見る
第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