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