はじめに

ITエンジニアなら、基本的なアルゴリズムは知っておきたいよねとか言われても、一つも知らなかった。

まず、なぜ知って起きたいほど重要なのかをハラ落ちさせたかったので色々調べてみた。

この記事に、アルゴリズムが大事だという２つ理由がありました。

速く基本的なアルゴリズムが正しく組める人は、他のコードを書かせてもバグを入れにくいうえ、作業が速い。もちろん、アルゴリズムを組むのが遅くても、バグの少ないコードを書く人は沢山いる。でも、アルゴリズムを速く正確に組める人は概して他のコードを書かせても素早いし、バグを入れにくい。雇う側からすれば、バグが少なく開発スピードが速いに越したことはない。

もう一つは

効率的なアルゴリズムはコスト削減につながる。当然の話だが、同じ機能だったら出来る限り少ないリソースでできた方が、コストが減って儲けにつながる。ソフトウェアもビジネスなので、コストが低いに越したことはない。そこで様々なソフトウェアの最適化がされるのだが、多くの場合、もっとも大幅にリソース使用量を減らせるのが、より効率的なアルゴリズムを使うことだ。裏を返せば、効率的なアルゴリズムがちゃちゃっと組めないエンジニアは、コードを書く度に、それだけ会社に損をさせていることになる。

アルゴリズムを勉強すると、応用力が効くし、コードの安全性も増すことができるということだろう。よし、ハラ落ち。

次に、本屋で簡単そうなアルゴリズムの本を買ったので、それを今勉強中のRubyで書いてみようというのをやって行こうかと思います。

今回は...

線形探索法

教科書はp90にあります。

線形探索法（リニアサーチ）は、探索アルゴリズムの一種です。探索アルゴリズムとは、目的のデータを探し出すアルゴリズムのことです。検索エンジンもこのアルゴリズムを利用しているみたいです。

線形探索法（リニアサーチ）とは

線形探索法（リニアサーチ）とは、単純にいうと先頭から順番に調べるアルゴリズムです。ただし、アルゴリズムの単純さゆえ、探索効率が他のルゴリズムと比較するとそれほどいいわけじゃないみたいです。

箱に入ってるボールが、何個も横に並んでるとします。ボールには番号が書いてあって、自分からは見えない。それを左から順番に、確認していく、これが線形探索法（リニアサーチ）のイメージです。

線形探索法（リニアサーチ）のアルゴリズム

ポイントは3つ

配列に保存されたデータを先頭（左）から順番に探索する
探索処理は反復構造
反復構造では終了条件をわすれずに

です。

箱に入ってるボールが、何個も横に並んでるイメージはこんな感じです。

処理の流れ

それぞれの値は、配列名（array）と、index番号を使って表せます。

例えば

array [0]

=> 4

という感じ。

配列の要素	値
array [0]	4
array [1]	2
array [2]	3
array [3]	5
array [4]	1

線形探索法（リニアサーチ）はシンプルに、上から比較して、あればその数字を返す。なければ「無い」というだけの単純なアルゴリズムです。それでは、それをrubyで記述していきます。

Rubyで線形探索法（リニアサーチ）を書いてみた


array = [ 4, 2, 3, 5, 1 ]
numbers_of_array = array.count

def linear_search(array, numbers_of_array, target)

  index = 0

  loop do
    if index == numbers_of_array
      return -1
    elsif array[index] == target
      return index
    end
    index += 1
  end
end

# 探したい値
target = 5

# メソッド（linear_search）
# array 引数 配列オブジェクト
# numbers_of_array 引数 配列の要素数
# target 引数
# result 戻り値の格納先
result = linear_search(array, numbers_of_array, target)

if result == -1
  puts "値:#{target}は配列内にありません"
else
  puts "値:#{target}のインデックス:#{result}"
end

linear_searchというメソッドに３つの引数を指定して、処理させて任意の値があれば、メソッドの下にあるif分のelse内を出力、なければresult == -1の結果を出力させてます。

以上です！行けてないコードであればご指摘ください。

レポジトリ

参考図書

伊藤静香. アルゴリズムを、はじめよう. 第3章. インプレス, 2012, p. 90-100.