*目的のデータを探すアルゴリズムを学ぶ
vue.jsの勉強を書籍使ってしていたところ、使っているノートPCのキーの反応がまったくなく修理に...
サンプルアプリは完成して落ち着いたので、苦手だったアルゴリズムの勉強を少しずつ進めていきたい。
探索アルゴリズムとは任意の数〇個のデータ（配列の）中から目的の値を探すアルゴリズム。
rubyを使って学んでいきます。
今回は探索アルゴリズムの中から基本の線形探索と二分探索について書いていく。
*線形探索（リニアサーチ）
array = [14,32,45,67,89,122]
例えば89という目的の数字を探したいアルゴリズム
目的のデータがどこにあるか？配列の先頭14から122まで順番に探す。
最初に14と89を比較、次に32と89を比較し89が見つかるまで比較する。
実際に線形探索のコードを書いてみる。
例題
def linear_search(array,target) array.each.with_index(1) do |num,index| if num == target puts "探している値は#{index}番目にあります" return end end puts "探している値はありませんでした。" end array = [24,30,45,67,90,12,454,100] linear_search(array,45) linear_search(array,5)
解説
array = [配列]を定義
linear_search(array,45)でdef linear_search(array,target)を呼び引数を入れる。
array.each.with_index(1)で配列内を順番に探索、indexは配列内の要素のインデックス
条件分岐を行いtarget例だと45が見つかったら出力
.each.with_indexについて
rubyのメソッドで通常のeachブロックから要素を取り出す際要素のインデックスは渡さないが
each.with_indexを使うことでインデックスを取得しながら要素を処理することができる。
例題だと(1)はインデックスの開始値を指定している。(0)にすると配列内の24のインデックスは0になる。
なのでeach.with_index(1)で24を出力すると探している値は1番目にありますとでる。
*二分探索（バイナリーサーチ）
探索対象のデータの探索範囲を半分にして目的のデータを探すアルゴリズム。
探索対象の配列内のデータはあらかじめ小さい順にしておく必要がある。
二分探索は目的の値が中心地より大きいほうに存在するか小さいほうに存在するか判断しながら探索する。
array = [14,32,45,67,89,122,245,367]
目的の値89とする
目的の値が配列の中心より大きいか小さいかを判断する。67より大きい？小さい
目的の値の方が大きければ配列の中心値より大きい方を残す。67より89のがおおきいから
[89,122,245,367]を残す。
目的の値(89)は中心値より小さい方を残すので[89,122]が残る
あとは繰り返し目的の値を探す。
例題
def binary_search(array,target) head= 0 tail = array.length - 1 while head <= tail center = (head + tail) /2 if array[center] == target puts "#{target}は#{center + 1}番目にありました" return elsif array[center] < target head = center +1 else tail = center - 1 end end puts "#{target}は見つかりませんでした。" end array = [14,32,45,67,89,122,245,367] puts"探索したい値を以下から選んで、入力してください。" puts array.join(",") target = gets.to_i binary_search(array,target)
解説
head 配列の探索範囲の先頭の位置
tail 配列の探索範囲の末尾の位置
center 配列の中央の位置
target 探索する値
とします。
配列arrayを作成。
①joinで配列の中から探索したい数を入力。入力した後はtargetに代入。binary_search(array,target)で引数を渡す。
②メソッドの引数に探索対象である配列の先頭head=0と末尾の位置を示すtail=array.length - 1変数を定義
③while文で繰り返し処理の実装。探索範囲を表すheadとtailは繰り返し処理のたびに
head=1,tail=8 head=2 tail=7と範囲が狭まるためhead <= tailの条件を満たす限り繰り返し処理が行われる。
④繰り返し処理内で中心値を定義するためcenter = (head + tail) /2を記述。
center は初めて (0 + 7) / 2 で計算。array = [14, 32, 45, 67, 89, 122, 245, 367]だと67
⑤array[center] == targetで探している変数targetの値を配列の中心地であるarray[center]を比較結果に応じて条件の分岐を行 う
targetと中心値が一致すると結果を出力。returnで繰り返し処理を抜ける。
⑥次にelsif array[center] < targetで入力したtargetが中心値より大きい場合の条件分岐を行う。
探索範囲を狭めるためhead = center +1を記述。
探索範囲の先頭を中央の要素より１つ右に移動する。head = 0、tail = 7、center = 3 の場合、中央の要素は配列の中で 67 。
そして、head =center + 1を実行すると、headは4になる
探索範囲は[89,122,245,367]になる
⑦else tail = center - 1でtargetが中心地array[center]より小さい場合の条件分岐
末尾tailをcenter -1, tail = center - 1 を実行すると、tail は 2 になり探索範囲は[14,32,45]
targetが32の場合の処理は
head= 0
tail = array.length - 1
center = (0 + 7) /2で3 [14,32,45,67,89,122,245,367]だと67で4
if array[cente] == target array[67] == 32ではない,elsif array[67] < 32でもないのでelseが実行
tail = center - 1は 7 = 4 - 1でtailは3に更新 配列内は[14,32,45,67]に
while文に戻り center = (head + tail) /2は center = (0 + 3) /2 になりcenter= 1に
array[center] == target はarray[1]== 1になり出力し処理を抜ける。
初期状態で head = 0、tail = 7 の配列 [14,32,45,67,89,122,245,367] が与えられる。
中央のインデックスを計算し、center = (0 + 7) / 2 = 3 となり、中央の要素は 67 になります。
中央の要素と target を比較し、一致しないため、67 は 32 よりも大きいことが分かります。
else ブロックが実行され、tail が center - 1 に更新され、tail = 3 となります。
while ループに戻り、新しい中央のインデックスが計算され、center = (0 + 3) / 2 = 1 となります。
中央の要素と target を比較し、一致するため、32 が見つかったことを示すメッセージが出力され、探索が終了します。
インプット３割→アウトプット７割を意識したいのでonenoteに書いてからブログに乗せています。
実際にはコードを書いているより自分なりの解釈と、解説を書いている方が何倍も長いです。
次回はアルゴリズムの基本構造パターンをまとめて記事にしたい。
