【アルゴリズムの勉強】Rubyで番兵法を用いた線形探索を書いてみる
アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。
番兵法とは
データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。
・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ
Rubyで実装
arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12] number_of_elements = arr.count def linear_search_with_sentinel_method(arr, number_of_elements, target) index = 0 arr[number_of_elements] = target loop do break if arr[index] == target index += 1 end if index == number_of_elements return -1 else return index end end target = 10 result = linear_search_with_sentinel_method(arr, number_of_elements, target) if result == -1 puts "値が#{target}の要素は配列内に存在しません" else puts "要素の値が#{target}のインデックス => #{result}" end