Rubyで二分岐検索を書いてみる

環境

Ruby2.6

はじめに

Rubyで書いた二分岐検索のコードについて、解説したいと思います。二分岐検索とは、簡単にいえば、たくさんのデータの中から探したいデータを、効率的に検索するためのアルゴリズムです。プログラミング言語を学習するとき、一度くらいは、二分岐検索のコードを書いたことがある人は多いかと思います。しかし、二分岐検索のアルゴリズムそのものは、仕事で使うことは殆どないかと思います。折角学習しても、殆どの人は、役に立てることがありません。それでも、言語の学習教材としては、うってつけのアルゴリズムだとは思います。

二分岐検索の詳細についてはこちらをご参照ください。
https://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2.html

コードの解説

gets.chomp.to_i

標準入力で入力した値を取得して、数値に変換します。getsしただけでは、改行コードがついているため、chompで改行コードを取り除きます。

ary.sort!

ランダムに作った配列を昇順にソートします。

mid = (str + fin) / 2

配列から真ん中の要素数を取得します。例えば、[1,2,3]の場合、真ん中の要素数は1です。[1,2,3,4,5]の場合は2になります。

when ary[mid] <  n then
    str = mid +1

配列の真ん中の要素と検索したい数値とを比較して、検索したい数値の方が大きい場合、真ん中の要素より下にある要素は、全て検索対象からごっそりと除外します。これで検索にかかる労力が半分になります。

when ary[mid] >  n then
    fin = mid -1

配列の真ん中の要素と検索したい数値とを比較して、検索したい数値の方が小さい場合、真ん中の要素より上にある要素は、全て検索対象からごっそりと除外します。これで検索にかかる労力が半分になります。

while str <= fin

while文でループさせながら、検索したい要素が存在する範囲を少しづつ、絞り込んでいきます。

when ary[mid] == n then 
    ans = mid
    break

検索したい要素を絞り込んでいった結果、遂に、検索したい要素が見つかれば、ループ処理から抜けます。

コード

ruby.rb

n = gets.chomp.to_i
ary = [1,6,44,99,3,56,74,12,89,45,80,7,34,56]
ary.sort!

# 初期化
ans = nil
str = 0
fin = ary.count - 1
mid = 0

while str <= fin

    mid = (str + fin) / 2

    case 
        when ary[mid] == n then 
            ans = mid
            break
        when ary[mid] <  n then
            str = mid +1
        when ary[mid] >  n then
            fin = mid -1
    end
end
if ans.nil? 
    puts "要素がありません"
else
    puts "#{ary}"
    puts "#{n}は上記配列の "+ ans.to_s + "番目の要素に存在します"
end

実行結果

[1, 3, 6, 7, 12, 34, 44, 45, 56, 56, 74, 80, 89, 99]
6は上記配列の 2番目の要素に存在します

[1, 3, 6, 7, 12, 34, 44, 45, 56, 56, 74, 80, 89, 99]
74は上記配列の 10番目の要素に存在します