読者です 読者をやめる 読者になる 読者になる

【アルゴリズムの勉強】Rubyで番兵法を用いた線形探索を書いてみる

アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。

番兵法とは

データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。
・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ

番兵 - Wikipedia

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

参考文献、参考リンク