リスト検索のアルゴリズムを実装する

アルゴリズムの基礎の基礎だが、考え方はともかくコードにするとどうなるのか考えたことがなかったのでrubyで実装してみた。

線形探索(linear search)

概要

一番単純な探索方法

• 最初から一個ずつ確認して該当するものを探し出す リストの中身がどんな並びでも使える

フローチャート

実装

def linear_search key, array
    found = false                    //検索値ががリストの中に存在しているか否か
    array.length.times do |i|
      if @array[i] == key
        found = true
        puts "#{key} は array[#{i}]にありました"
        break
      end
    end
    if found == false
      puts "#{key}は見つかりませんでした"
    end
  end

特に問題になることもないですね。

二分探索(binary search)

概要

ソートされているリストでの検索方法 リストの中央の値を取り出して、検索値と比較し、取り出した値よりも前に存在するのか後に存在するのかを絞り込む。 絞り込んだ中から中央の値を取り出して比較して・・・ というふうに範囲を絞りながら検索する方法だ。 リストの中に検索値が存在しなくてもリスト全部にアクセスせずに済む。

実装

def binary_search_tree key, array
    found = false             //検索値ががリストの中に存在しているか否か
    left = 0                        //絞り込む範囲の開始位置
    right = array.length   //絞り込む範囲の終了位置
    while left < right        //開始位置と終了位置が重なったら（絞込範囲が０になったら）ループ終了
      half_point = (left + right) / 2
      if array[half_point] == key
        found = true
        break
      else
        array[half_point] < key ? left = half_point + 1 : right = half_point
      end
    end
    if found
      puts "#{key}はarray[#{half_point}]にありました"
    else
      puts "#{key}は見つかりませんでした"
    end
  end
end

ループの終了条件が悩みどころだった。 検索範囲を絞り込むということで、検索範囲を別のリストにしようかとも考えたがリスト自体には手を加えないこちらの方がスマートに感じる。