【Ruby】バイナリーサーチを使用して配列内の要素の検索

概要

少々複雑に感じることも言語化することで理解をを深くできると思いまとめました。もっと良い表現や間違えなどご指摘いただけたら幸いです。

目次

• バイナリーサーチとは

  • 検索プロセス

• 実践

  • 問題
  • 解答

• まとめ

• 参考文献

バイナリーサーチとは

ソート済みのリストや配列に入ったデータを検索するときに使用する手法です。対象のデータを半分に絞り込むことで検索していきます。

検索プロセス

• 二分割したときの値と検索したいデータが一致するまで繰り返し検索するように while を使用

  • 検索したいデータが半分より右にあるか？　左にあるか？
  • もしくは配列内に存在しないのか？

実践

問題

配列に任意の値が存在するかどうか、そして何番目に存在するのか、検索してください。

解答

def binary_search(ary, target)

  left = 0                # 配列は0番目スタート
  right = ary.length - 1  # 配列の最後尾（番目）

  while left <= right           # 目的の値を見つけるまで
    center = (left + right) / 2 # 配列の真ん中を取得

    if ary[center] == target                              # 配列の添字と検索したい数字が揃ったら
      return "#{target}は配列の#{center + 1}番目に存在します"  # returnで結果を返す

    elsif ary[center] < target # 検索したい数字が半分より右側にあったら
      left = center + 1        # 半分より右側を検索するように添え字に1を足す

    else                       # 検索したい数字が半分より左側にあったら
      right = center - 1       # 半分より左側を検索するように添え字から1を引く
    end
  end

  return "#{target}は配列内に存在しません" # whileの条件を外れ、検索に引っかからなかった時
end

# 配列
ary = [1, 3, 5, 6, 9, 14, 24, 33, 45, 53]

# ターミナルで検索したい数字を入力する
p '検索したい数字を入力してください'

# 数字なのでto_iを使用
target = gets.to_i

# ソート済みの配列と検索したい数字をbinary_searchメソッドに渡す。
p binary_search(ary, target) 

まとめ

• バイナリーサーチとはソート済みのリストや配列に入ったデータを検索するときに使用する手法
• 二分割しながら値を絞り込む

参考文献

• Rubyで二分探索法（バイナリサーチ）を書いてみた