はじめに

この記事では2分探索についてRubyで解説していきます。

2分探索とは

2分探索は要素がキーのの昇順や降順に整列(ソート)している配列から効率よく探索を行うアルゴリズムです。
2分探索はバイナリーサーチとも呼びます。

実装例

2分探索をRubyで実装していきます。

binary_search.rb

# 配列aの先頭number個からtargetと一致する要素を2分探索(探索が失敗したら-1を返す）

def binary_search(a , number, target )
  first_index = 0 #探索範囲先頭の要素
  last_index  = number - 1 #探索範囲末尾の要素

  begin
    center_index = (first_index + last_index) / 2 #中央の要素
    if a[center_index] == target
      return center_index #探索成功
    elsif a[center_index] < target
      first_index = center_index + 1 #探索範囲を後半に絞り込む
    else
      last_index  = center_index - 1 #探索範囲を前半に絞り込む
    end
  end while first_index <= last_index

  -1 #探索失敗
end

puts "要素数を入力してください。"
print "要素数："
number = gets.to_i
a = []

puts "昇順に入力してください。"
print "a[0]：" #先頭の要素を先に読み込む
a[0] = gets.to_i

# 昇順に入力する
(1..number - 1).each {|i|
  print "a[#{i}]："
  a[i] = gets.to_i
  redo if a[i] <= a[i - 1] #1つ前の要素より同じか小さければ再入力
}


puts "探す値を入力してください。"
target = gets.to_i

result = binary_search(a, number, target)

if result == -1
  puts "その値は存在しません。"
else
  puts "その値はa[#{result}]にあります。"
end

コードの解説

では上記のコードの解説をしていきます。

1.昇順の配列aを用意する

まず最初に昇順で数字が並んでいる配列aがを用意します。
ここでは、配列は標準入力を利用して用意しています。

2.配列の中央にある要素を調べる。

次にbinary_searchメソッドで配列の中央にある要素を調べます。
先頭の要素(first_index)と末尾の要素(last_index)を足して2割ったものが中央にある要素(center_index)となります。

3.探索する

では、いよいよ探索を開始します。

中央の要素が目的の値の場合

中央の要素(center_index)が目的の値(target)の場合はそこで探索が終了します。

目的の要素が中央の要素より小さい場合

探索範囲を配列aの後半に絞り込み探索を続けます。

目的の要素が中央の要素より大きい場合

探索範囲を配列aの前半に絞り込み探索を続けます。

探索が失敗する場合

探索を繰り返していき先頭の要素(first_index)が末尾の要素(last_index)以上になってしまった場合、その時点で配列aのなかに目的の要素が無いということが分かるので探索失敗です。

以上でコードの解説を終了します。

最後に

以上で2分探索についての解説を終了します。
何か間違っていることがあったらご指摘ください

参考

以下の書籍を参考にしました。

新・明解 Javaで学ぶアルゴリズムとデータ構造
https://www.amazon.co.jp/%E6%96%B0%E3%83%BB%E6%98%8E%E8%A7%A3-Java%E3%81%A7%E5%AD%A6%E3%81%B6%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%9F%B4%E7%94%B0-%E6%9C%9B%E6%B4%8B-ebook/dp/B0722XVC7D/ref=tmm_kin_swatch_0?_encoding=UTF8&qid=&sr=