アルゴリズムを始めよう(リニアサーチ バイナリサーチ)

言語とフレームワークの勉強の他に実際にプログラミングの発想をだすための下地
が必要だと感じ、アルゴリズムを勉強する。教科書はこれ

アルゴリズムを、はじめよう

リニアサーチ

本によると、めちゃくちゃ単純な検索方法で1つずつ箱を開けていき、目当ての
ものを探っていく。ポイントは配列に格納している添字を処理が終わるごとに足して行くこと。

Rubyで書いてみた

a = [17, 18, 20, 21, 23] #=>この5つの要素から21を探したす
i = 0　#=>探索のポイント。これを動かして行くことで全部の要素を調べる
while i < 4 do　#=>5つの要素で0から4までの添字を持つから
    if a[i] == 21
        puts "#{i}に要素がありました"
        break
    else
        i += 1　#=>添字をずらし、要素をずらす
    end
end

breakがないとループするので注意が必要。それ以外は特に目新しくない。この探索は1つ１つ調べていくのでやたら時間がかかるらしい。

バイナリサーチ

検索方法は少しややこしい。前提としてバイナリサーチのデータはソートされていることが必要。配列の真ん中（center）の要素と探したい要素を比較し、同じか大なりか小なりかで判断。もちろん同じ場合は見つけた！となりそこで終了。探したい要素> 配列の真ん中の要素　場合　今度の探索場所は真ん中より右よりの範囲で探す。反対に探したい要素 < 配列の真ん中の要素　場合　今度の探索場所は配列の真ん中より左の範囲で探すことになる。
この探す範囲を徐々に絞って行く動きを作るために、配列の先頭(head)と配列の最後尾(tail)が重要になってくる。

範囲の動き

配列の真ん中の添え字を得るには配列の先頭（head）と最後尾（tail）を足して２で割ると真ん中になる。
では最初に調べた真ん中が該当しない場合、次の真ん中はどうやって確定すればいいのか。

探している要素が真ん中の要素より小さい要素の場合
次に探したい場所は真ん中より左側になる
そのため、次に探したい要素のtailはさっきの真ん中から見ると、-1の添え字になる。これで次に調べたい範囲のheadとtailが確定する。

探している要素が真ん中の要素より大きい要素の場合
次に探したい場所は真ん中より右側になる
そのため、次に探したい要素のheadはさっきの真ん中から見ると、+1の添え字になる。これで次に調べたい範囲のheadとtailが確定する。

バイナリサーチではこの範囲の絞り方が発想できなかった。

Rubyで書いてみた

a = [17, 18, 20, 21, 23, 25, 31]　# => この配列から17を見つけるようにする。
head = 0　# => 範囲を定めるためのhead　配列の先頭の添字
tail = 6　# => 範囲を定めるためのtail 配列の最後の添字
while head <= tail  do　#=> 繰り返し探索を続ける
   center = (head + tail) / 2
    if a[center] == 17
        puts "OK"
        break
        elsif a[center] > 17
        tail = center - 1
        elsif a[center] < 17
        head = center + 1
         if head > tail
             puts "なし"
             break
         end
    end
end

ポイントはheadとtailとcenterで範囲を絞っていくこと。一番わかりづらかったのは、while head <= tail do　のところ。次の範囲の探索は必ず、centerを起点に右範囲か左範囲になるかを考える。そうすると徐々に範囲が狭まってくる。狭まると、どこかでheadとtailが逆転することが起こりうる。逆転の範囲はありえないから、探索は逆転の範囲が終了するまで続けることになる。