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

アルゴリズム Ruby

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

線形探索とは

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
{\displaystyle n} n個のデータから {\displaystyle m} m個のデータを検索する場合、 時間計算量は {\displaystyle O(nm)} O(nm)、空間計算量は {\displaystyle O(1)} O(1)必要となる。

線型探索 - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count

def linear_search(arr, number_of_elements, target)
  index = 0
  loop do
    if index == number_of_elements
      return -1
    elsif arr[index] == target
      return index
    end
    index += 1
  end
end

target = 9
result = linear_search(arr, number_of_elements, target)
if result == -1
  puts "値が#{target}の要素は配列内に存在しません"
else
  puts "要素の値が#{target}のインデックス => #{result}"
end

参考文献、参考リンク