「力ずくで検索」リニアサーチ

サーチ(検索)とは

サーチとは、たくさんのデータの中から目的のデータがどこにあるか調べる作業である。

リニアサーチ

リニアサーチとは、要は「力ずくの検索」のことである。線形探索という。計算量オーダはO(N)。
先頭から順番に調べていって、探している数値と同じかどうかを確認。
探している数値が見つかったら場所を返すというもの。

リニアサーチするRubyのサンプル

# -*- encoding: utf-8 -*-

def lenear_search(array, target_num)
  array_size = array.size()
  for num in 0..(array_size - 1)
    if (target_num == array[num])
      puts "一致しました！！！"
      p "indexは", num
      return num
    end
  end
  puts "ごめんなさい。一致しませんでした・・・"
  return -1
end


array = [];
for num in 1..300 do
  array << (rand() * 500).to_i
end

puts "配列のサイズは・・・"
puts array.size()
puts "---------"

target_num = 95
puts "目的の数字は・・・・"
puts target_num
puts "---------"

puts "リニアサーチを開始します！"
index = lenear_search(array, target_num)

puts "------"
if index != -1
  puts "目的の数字は・・・"
  puts array[index]
  puts "ですね？"
end

lenear_searchメソッドに、配列とターゲットの数字を渡して、目的の数字がどのインデックスに存在するかを調べる。
先頭から順に力ずくで一致するかどうかを調べているのがわかる。

値が見つかった時の結果は、以下の通りになる。

配列のサイズは・・・
300
---------
目的の数字は・・・・
95
---------
リニアサーチを開始します！
一致しました！！！
"indexは"
145
------
目的の数字は・・・
95
ですね？

値が見つからなかった時の結果は以下の通り。

配列のサイズは・・・
300
---------
目的の数字は・・・・
95
---------
リニアサーチを開始します！
ごめんなさい。一致しませんでした・・・
------

勉強した本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

感謝のプログラミング

今回で感謝のプログラミングは【594時間目】
10000時間まで、あと【9406時間】