Header
2020-02-01
2020-03-08

Rubyで二分探索(バイナリサーチ)を行う

2020 02 01 ruby algorithm

二分探索(バイナリサーチ)とは

ソートされたリストや配列の中央値を検索し、それを繰り返していく検索アルゴリズムです。

基本的には以下の数式を繰り返していく形です。

 最小位置 + (最大位置 - 最小位置) / 2 

Rubyで二分探索(バイナリサーチ)を行う際のサンプルコード

以下がサンプルコードです。

def binary_search(array, value)
  min_index = 0           # 開始のインデックス番号
  tail = array.length - 1 # 末尾のインデックス番号
  while min_index <= tail
    center = ((min_index + tail) / 2.0).round #中央のインデックス番号(7が対象)
    if array[center] == value
      return p "指定値のインデックス番号は#{center}"
    elsif array[center] < value
      min_index = center + 1
    else
      p center  # インデックス番号3が出力
      tail = center - 1
    end
  end
  return "該当値がありません"
end

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
value = 3

binary_search(array, value)

二分探索(バイナリサーチ)サンプルコードの重要な解説

Rubyの配列のインデックス番号の初期値は0から開始されます その為Rubyで二分探索を行う場合の数式は以下になります。

(最大位置 - 最小位置) / 2

該当するコードは以下になります。

 ((min_index + tail) / 2.0).round 

あとは以下で繰り返し処理で回していく形になります。

    if array[center] == value
      return p "指定値のインデックス番号は#{center}"
    elsif array[center] < value
      min_index = center + 1
    else
      p center  # インデックス番号3が出力
      tail = center - 1
    end

参考

Rubyで2分探索

その他関連記事

Rubyの引数で使えるテクニック|キーワード引数

初心者・独学者向け|Rubyのハッシュ入門とよく使うメソッド

初心者・独学者向け|Rubyの配列処理の入門とよく使うメソッド

初心者・独学者向け|Rubyのinitializeメソッドとは

初心者・独学者向け|RubyのStringクラスとよく使うメソッド

Rubyの繰り返し処理の解説|初心者・独学者向け

paiza(パイザ)Cランク練習問題|5以上の整数の合計のRubyサンプルコードと解説

前の記事
次の記事
人気記事
カテゴリーから記事を探す