はじめに

今回はこちらの本でアルゴリズムの勉強をしているので学んだことをRubyで書いて見ました。
アルゴリズムをはじめよう
こちらの記事を参考にさせていただいてます。
Rubyで二分探索法（バイナリサーチ）を書いてみた

二分探索法

二分探索法は予め、昇順か降順に整列されているデータが対象で、探索する範囲を半分に絞りながら探索を進めます。
手順は
①配列の真ん中の要素を求める
②真ん中のデータと目的のデータを比較する（一致したら探索終了。一致しない場合③へ）
③比較したデータが目的のデータより大きいか小さいか確認して探索の範囲を半分に狭める。
以降①→③を繰り返す。

配列の真ん中の要素を求める為に「head」と「tail」という二つの変数を用意。
真ん中を求めるには配列の先頭と末尾を足して２でわる。割り切れない場合は小数点を切り捨てます。（整数型の場合自動的に切り捨てになります。）

はじめに書いたコードはこんな感じでした。

def binary_search(array,target)
    #配列の真ん中を求める為下準備
    head =0
    tail =(array.count)-1

    loop do
        if head <= tail
          #①配列の真ん中の要素を求める
          center = (head+tail)/2
          #②真ん中のデータと目的のデータを比較する（一致したら探索終了。一致しない場合③へ）
          if array[center] == target
            return center
          #③比較したデータが目的のデータより大きいか小さいか確認する。
          else
            if array[center] < target
                head =center+1
            else
                tail =center-1
            end
          end
        else 
            #目的の値が見つからない場合−1を返す。
            return -1
        end
    end
end

テスト

require 'minitest/autorun'
require './irb/binary.rb'

class BinaryTest < Minitest::Test
  def test_binary
    assert_equal  6,binary_search([11,13,17,19,23,29,31],31)
    assert_equal  -1,binary_search([11,13,17,19,23,29,31],35)
    assert_equal  0,binary_search([11,13,17,19,23,29,31],11)
    assert_equal  0,binary_search([11,13,17],11)
    assert_equal  -1,binary_search([11,13,17],15)
    assert_equal  3,binary_search([11,13,17,67],67)
  end  
end

テスト実行。

ruby test/binary_test.rb
Finished in 0.000620s, 1612.9031 runs/s, 9677.4184 assertions/s.

1 runs, 6 assertions, 0 failures, 0 errors, 0 skips

リファクタリング

途中でloopメゾットを使っていますが、条件が真である間処理を繰り返すwhile文を使う等して見やすいコードにしました。

def binary_search(array,target)
  head =0
  tail =(array.count)-1

    while head <= tail
      center = (head+tail)/2

      if array[center] == target
        return center

      elsif array[center] < target
        head =center+1
          
      else
        tail =center-1
      end   
    end
    return -1
end

※フォルダ構成はこのようにしてあります。

ruby
├── irb  
│   └── binary.rb
└── test
    └── binary_test.rb

最後までお読みいただきありがとうございました。アドバイス等あればコメントいただけると幸いです。