Rubyで二分探索

ソート済み配列から目的の値を効率よく探す、二分探索（バイナリサーチ）の実装例です。コピペで動くコードと実行結果、処理の流れを確認できます。 下のコードはブラウザ内でそのまま実行できます。「実行エディタで開く」を押すと、progoのオンラインRuby実行環境にコードが読み込まれ、その場で動作を確認できます。

サンプルコード

arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
low, high = 0, arr.length - 1
result = -1
while low <= high
  mid = (low + high) / 2
  if arr[mid] == target
    result = mid
    break
  elsif arr[mid] < target
    low = mid + 1
  else
    high = mid - 1
  end
end
puts "インデックス: #{result}"

ポイント解説

• 中央インデックスを整数除算で求めます。
• low/highを更新しながら絞り込みます。
• 見つかったらbreakで終了します。