「アルゴリズムをはじめよう 」(伊藤静香著)を読んだので、備忘録的まとめ

線形探索法 

特徴
先頭から順々に探すアルゴリズム
単純でわかりやすい
効率はあんまよくない

とりあえず試しに、8が左から何番目にあるかを線形探索法で探すアルゴリズムを組んでみた

num = "12345676545671287440278174913740971846071467384127346120365107246571647016183640712365876407871473"
ary = num.split('').map(&:to_i)

i = 0
while i < ary.size
  i += 1
  break if ary[i] == 8
end

puts i

まず適当に数字を打ち込む(探索する対象として用意)
splitメソッドで配列として変数aryに格納
探索の終了条件を決める。今回は配列aryから8を見つけるか、全部探し切ったら終わりってことにする。

変数iをおき、aryを左から一個ずつ数字をみていく。
一個見るたびにi君は一つまた一つと成長し、その度に視座も高くなっていく。(見る数字が一個ずつ左にずれていく)

i君が8を見つけた時点でループ終了
その時のiに入ってる数字を出力して、一番左側の8の場所を見つけることができました。

線形探索じゃないかもだけど、

ary.each_with_index do |n,i|

  if n == 8
    puts "8は#{i}番目にあります"
  end
end

これで、配列の中の全部の8の場所を探せる。
これはeach_with_indexメソッドで添字を取得しているだけだから簡単だけど、一番左側の8の場所だけ取り出したい時がなんかわからんかった。

もうちょっと研究します。

二分探索法

特徴
あらかじめソートされているデータが対象
探索する範囲を半分にしながら探索する

プロセスとしては
①真ん中の要素を選ぶ作業
②真ん中のデータと目的のデータを比較する作業
③探索の範囲をもう半分に狭める作業
がある。

ary = "1,2,13,56,213,14253,1213421,2123313,141235253,2415245346513"
a = ary.split(',').map(&:to_i)

h = 0
t = a.size - 1
w = 213

while h <= t
  c = (h + t)/2
  if a[c] == w
    puts c - 1
  elsif  a[c] < w
    h = c + 1
  elsif a[c] > w
    t = c - 1
  end
  break if a[c] == w
end

とりあえず書いてみた。
まず探索する範囲のデータを用意し、配列として格納。
今回探索する目的の数字は213とした。

探索範囲の最初をh,終わりをtと置く。
探索範囲に対象物がなかった場合、処理を続けるとhとtの値の関係性が逆転するので、それを見つからなかった時の終了条件とする。
まず(h+t)/2で探索範囲の中心を探す。これをcと置く。
c番目の数が213だったら処理を終了。213の位置を出力する。
違った場合、cと213を比較し、大小の場合それぞれで場合わけする。
そんでhもしくはtの値を変更し、同じ処理を繰り返す。
対象が見つかったら処理を終わらせる。

いい感じ。

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.