アルゴリズム線形検索と二分検索の違い

線形検索アルゴリズム

線形検索アルゴリズムとは、配列からデータを検索するアルゴリズムです。
線形検索は配列がソート（整列）されていない場合にも適応することができることが特徴です。
配列から検索できるのは線形検索と二分検索ですが、これらの何が違うのでしょうか。

線形検索と二分検索の違い

これらの違いは、処理の仕方が異なるということです。
目的は同じで配列の中から結果を出しますが、処理の内容が異なるので、処理の完了までの時間も異なります。

二分検索

二分検索の処理はソートされているのが、条件の一つになります。
ソートされている状態で、配列の中央からデータを分割にして値の検索を行います。

線形検索

線形検索は、二分検索と異なり、配列がソートされていない状態での検索が可能になります。
検索開始地点は配列の先頭から検索していく特徴があります。

       1, １０, ４, ８, 5, ７, ６, ３, 9, ２
     　→１から順番に期待している値を検索する

線形検索の特徴は、
・ソートする必要がないこと。
・ソートされていない配列に適応することができること。
・左から順番に検索を行うので、データが大きい時や期待しているデータが最後にある時は処理が二分検索に比べて長くなってしまうこと。

１が最初に来て期待する値も１あれば、二分検索よりも早い処理をしますが、大きいデータや最後にあるデータを見つけつとなると線形検索は劣ってしまうことです。

Rubyのコードを書いてみる

rubyをコードで表すとこのようになります。
indexメソッドは配列を左から処理をするメソッドの一つです。

  array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  target = 6
  result = array.index(target)

  if result
    puts "#{target}は#{result + 1}番目にある"
  else
    puts "#{target}は配列には存在しない値"
  end

最後に

処理の期待する値が同じでも処理が異なると、速さも変わってくると思うとどの場面に適応すべきかなど理解できるようになったと思います。
わかりにくいことがあったり、アドバイスがあればコメントお願いします。