はじめに
この記事ではRubyで線形探索について解説していきます。
線形探索とは
線形探索とは最も単純なアルゴリズムの一つで、目的とする要素に出会うまで先頭から順に要素を走査(なぞるように探す)していくことです。
もっと単純に言うと先頭から末尾まで一つ一つ探していきます。
線形探索では値があるか、値はどこにあるかなどを求めることができます。
また線形探索は逐次探索やリニアサーチとも言います。
メリットとデメリット
メリット
線形探索のメリットは単純で実装がしやすいと言うことです。
デメリット
線形探索のデメリットは先頭から末尾まで一つ一つ調べるので処理が遅いと言うことです。
実装例
下記のコードでは線形探索の例を書いています。
# 配列aの先頭number個の要素からtargetと一致する要素を線形探索
def linear_search(a, number, target)
#探索に失敗した場合は-1を返す
i = 0
loop do
return -1 if i == number #探索成功
return i if a[i] == target #探索失敗
i += 1
end
end
puts "配列aの要素数を入力してください。"
number = gets.to_i
a = []
puts "配列に入る数字を入力してください"
number.times {|i|
print "a[#{i}]："
a[i] = gets.to_i
}
puts "探したい値を入力してください"
print "探す値："
target = gets.to_i
result = linear_search(a, number, target)
if result == -1
puts "その値は存在しません。"
else
puts "その値はa[#{result}]にあります。"
end
番兵法
番兵法とは探索する値と全く同じ値を、配列の一番後ろに置く探索の方法のことです。
番兵とは、そのとき格納する「探索する値と全く同じ値」のことのことです。
番兵を置く理由は探索するときのコストを抑えることです。
前回書いたの線形探索のコードでは、探索するときに毎回if文を2回繰り返します。
def linear_search(a, number, target)
#探索に失敗した場合は-1を返す
i = 0
loop do
return -1 if i == number #探索成功
return i if a[i] == target #探索失敗
i += 1
end
end
一方番兵法を使えばif文は1つですみます。
def linear_search(a, number, target)
#探索に失敗した場合は-1を返す
i = 0
a[number] = target #番兵を追加
loop do
break if a[i] == target #探索成功
i += 1
end
i == number ? -1 : i
end
最初のinear_search.rbに書いた線形探索では探索が成功したか判定するif文と探索が失敗したか判定するif文の2回を何度も繰り返します。
一方、linear_search2.rbに書いた番兵法では探索が成功した場合は、その時点で探索が終了します。これは線形探索と同じです。
そして探索が失敗したか判定するときは、線形探索ではなんども繰り返し判定していましたが、番兵法では末尾に番兵として目的の値が加えられているため、目的の値がない場合最後の探索で終了条件が成立します。
これにより、何度も終了条件を判定する必要がなくコストを抑えられます。
実装例
下記のコードが番兵法の実装例です。
def linear_search(a, number, target)
i = 0
a[number] = target #番兵を追加
loop do
break if a[i] == target #探索成功
i += 1
end
i == number ? -1 : i
end
puts "配列aの要素数を入力してください。"
number = gets.to_i
a = []
puts "配列に入る数字を入力してください"
number.times {|i|
print "a[#{i}]："
a[i] = gets.to_i
}
puts "探したい値を入力してください"
print "探す値："
target = gets.to_i
result = linear_search(a, number, target)
if result == -1
puts "その値は存在しません。"
else
puts "その値はa[#{result}]にあります。"
end
最後に
以上で線形探索と番兵法についての解説を終わります。
何か間違っていることがあったらご指摘ください。
参考
以下の書籍を参考にしました。