線形探索法(linear search)とは
線形探索法(linear search)は、沢山のデータを一直線に並べて先頭（又は末尾）から順番に調べて、特定のデータを見つけ出すアルゴリズムです。
結果を記録する変数を用意してデータを順番に調べていき、特定のデータがあれば結果の変数を更新する流れで実装出来ます。
イメージとしてはシャッフルされたトランプの山があって、その中から特定のカードを探すために上から1枚ずつめくっていくような感じになります。
特定の値が有るか無いかを調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中に、対象の値 k=6が有るか無いかを調べる。
処理の流れ
- 探索結果を
result=falseで初期化する 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx]==k(6)がtrueならresult = trueで更新する - breakでループから抜ける
(有無の確認なので、見つかった時点でその後の探索は不要)
- もし
- 探索結果
resultを確認する（trueなら有り / falseなら無し)
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = false
0.upto(n - 1) do |idx|
if a[idx] == k
result = true
break
end
end
p result
# > true
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = false
a.each do |num|
if num == k
result = true
break
end
end
p result
# > true
サンプルコード3
include?メソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] k = 6 p a.include?(k) # > true
特定の値が何個有るかを調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中に、対象の値 k=6が何個有るかを調べる。
処理の流れ
- 探索結果を
result=0で初期化する 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx]==k(6)がtrueならresult += 1で更新する
- もし
- 探索結果
resultを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = 0
0.upto(n - 1) do |idx|
if a[idx] == k
result += 1
end
end
p result
# > 2
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = 0
a.each do |num|
if num == k
result += 1
end
end
p result
# > 2
サンプルコード3
countメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] k = 6 p a.count(k) # > 2
特定の値がどこにあるかを調べる
先頭から見たときに最初に現れる添え字を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中で、先頭からみた時に最初に対象の値 k=6が現れる場所の添字を調べる。
処理の流れ
- 探索結果を
result=nilで初期化する
(探索で絶対に出てこない値に設定する) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx]==k(6)がtrueならresult = idxで更新する - breakでループから抜ける
(ループを抜けないとk(6)が複数あった場合、resultを上書きしてしまう)
- もし
- 探索結果
resultを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = nil
0.upto(n - 1) do |idx|
if a[idx] == k
result = idx
break
end
end
p result
# > 3
サンプルコード2
each_with_indexメソッドで配列の値と添字を先頭から順に参照する方法
result = nil
a.each_with_index do |num, idx|
if num == k
result = idx
break
end
end
p result
# > 3
サンプルコード3
indexメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] k = 6 p a.index(k) # > 3
先頭から見たときに最後に現れる添え字を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中で、先頭からみた時に最後に対象の値 k=6が現れる場所の添字を調べる。
処理の流れ
- 探索結果を
result=nilで初期化する
(探索で絶対に出てこない値に設定する) 配列 aの末尾から順に参照するループを設定する
(添字 idxを9(n - 1) から 0の間でカウントダウンしてa[idx]を参照)- もし
a[idx]==k(6)がtrueならresult = idxで更新する - breakでループから抜ける
(ループを抜けないとk(6)が複数あった場合、resultを上書きしてしまう)
- もし
- 探索結果
resultを確認する
サンプルコード1
添字を使って配列の末尾から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = nil
(n - 1).downto(0) do |idx|
if a[idx] == k
result = idx
break
end
end
p result
# > 8
サンプルコード2
each_with_indexメソッド、reverse_eachメソッドで配列の値と添字を末尾から順に参照する方法
（わざわざこうして実装する必要はないと思いますのでご参考まで...）
result = nil
a.each_with_index.reverse_each do |num, idx|
if num == k
result = idx
break
end
end
p result
# > 8
サンプルコード3
rindexメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] k = 6 p a.rindex(k) # > 8
対象の値が現れる全ての添え字を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中で、対象の値 k=6が現れる全ての添字を調べる。
処理の流れ
- 探索結果を
result=[]で初期化する
(複数の値が入る可能性があるので、空の配列を設定する) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx]==k(6)がtrueならresultにidxを追加する
- もし
- 探索結果
resultを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
result = []
0.upto(n - 1) do |idx|
if a[idx] == k
result << idx
end
end
p result
# > [3, 8]
サンプルコード2
selectメソッドを使う方法(2種類)
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
k = 6
# example1
p 0.upto(n - 1).select { |idx| a[idx] == k }
# > [3, 8]
# example2
p a.each_index.select { |idx| a[idx] == k }
# > [3, 8]
最小値・最大値を調べる
最小値を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中から最小値を調べる。
処理の流れ
- 探索結果を
min_num=Float::INFINITYで初期化する
(プラス無限大+∞で初期化することで先頭の値を初期値にする) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx] < min_numならmin_num = a[idx]で更新する
- もし
- 探索結果
min_numを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_num = Float::INFINITY
0.upto(n - 1) do |idx|
if a[idx] < min_num
min_num = a[idx]
end
end
p min_val
# > 1
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_num = Float::INFINITY
a.each do |num|
if num < min_num
min_num = num
end
end
p min_num
# > 1
サンプルコード3
minメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] p a.min # > 1
最大値を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中から最大値を調べる。
処理の流れ
- 探索結果を
max_num=-Float::INFINITYで初期化する
(マイナス無限大-∞で初期化することで先頭の値を初期値にする) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx] > max_numならmax_num = a[idx]で更新する
- もし
- 探索結果
max_numを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
max_num = -Float::INFINITY
0.upto(n - 1) do |idx|
if a[idx] > max_num
max_num = a[idx]
end
end
p max_num
# > 9
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
max_num = -Float::INFINITY
a.each do |num|
if num > max_num
max_num = num
end
end
p max_num
# > 9
サンプルコード3
maxメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] p a.max # > 9
最小値と最大値を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中から最小値と最大値を調べる。
処理の流れ
- 探索結果を初期化する
min_num=Float::INFINITY(プラス無限大+∞で初期化することで先頭の値を初期値にする)
max_num=-Float::INFINITY(マイナス無限大-∞で初期化することで先頭の値を初期値にする)
配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx] < min_numならmin_num = a[idx]で更新する - もし
a[idx] > max_numならmax_num = a[idx]で更新する
- もし
- 探索結果
min_num, max_numを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_num = Float::INFINITY
max_num = -Float::INFINITY
0.upto(n - 1) do |idx|
if a[idx] < min_num
min_num = a[idx]
end
if a[idx] > max_num
max_num = a[idx]
end
end
p [min_num, max_num]
# > [1, 9]
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_num = Float::INFINITY
max_num = -Float::INFINITY
a.each do |num|
if num < min_num
min_num = num
end
if num > max_num
max_num = num
end
end
p [min_num, max_num]
# > [1, 9]
サンプルコード3
minmaxメソッドを使う方法
n = 10 a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5] p a.minmax # > [1, 9]
条件を組み合わせて調べる
偶数かつ最小値を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中から偶数かつ最小値を調べる。
処理の流れ
- 探索結果を
min_even=Float::INFINITYで初期化する
(プラス無限大+∞で初期化することで最初に出た偶数値を初期値にする) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx] < min_evenかつa[idx]%2==0ならmin_even= a[idx]で更新する
- もし
- 探索結果
min_evenを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_even = Float::INFINITY
0.upto(n - 1) do |idx|
if a[idx] < min_even && a[idx] % 2 == 0
min_even = a[idx]
end
end
p min_even
# > 2
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
min_even = Float::INFINITY
a.each do |num|
if num < min_even && num % 2 == 0
min_even = num
end
end
p min_even
# > 2
サンプルコード3
selectメソッド、minメソッドを使う方法
※ スッキリ書けるのですが、selectを行ってからminを行うのでサンプル１・２より処理が遅いです。
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
p a.select { |num| num.even? }.min
# > 2
奇数かつ最大値を調べる
問題
データ数 n=10の配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中から奇数かつ最大値を調べる。
処理の流れ
- 探索結果を
max_odd=-Float::INFINITYで初期化する
(マイナス無限大-∞で初期化することで最初に出た奇数値を初期値にする) 配列 aの先頭から順に参照するループを設定する
(添字 idxを0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)- もし
a[idx] > max_oddかつa[idx]%2!=0ならmax_odd=a[idx]で更新する
- もし
- 探索結果
max_oddを確認する
サンプルコード1
添字を使って配列の先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
max_odd = -Float::INFINITY
0.upto(n - 1) do |idx|
if a[idx] > max_odd && a[idx] % 2 != 0
max_odd = a[idx]
end
end
p max_odd
# > 9
サンプルコード2
eachメソッドで配列の値を先頭から順に参照する方法
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
max_odd = -Float::INFINITY
a.each do |num|
if num > max_odd && num % 2 != 0
max_odd = num
end
end
p max_odd
# > 9
サンプルコード3
selectメソッド、maxメソッドを使う方法
※ スッキリ書けるのですが、selectを行ってからmaxを行うのでサンプル１・２より処理が遅いです。
n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]
p a.select { |num| num.odd? }.max
# > 9
今回のまとめ
線形探索法の手順
- 結果記録用の変数を準備して適切な値で初期化する
- 繰り返し処理でデータの探索を行い、条件分岐で結果記録用の変数を上書きする
- 必要に応じてループを抜ける処理を入れる
- ループを抜けた後、結果記録用の変数を確認する
複数条件の探索
- 繰り返し中の条件をアンド(&&)で繋げば複数条件に対応できる
- メソッドを繋げると（メソッドチェーン）スッキリ書けるが処理速度は遅くなる
線形探索は流れが単純なので実装しやすいですが、要素数が大量になると探索に時間がかかるという弱点もあります。
線形探索に慣れてきたら他の探索アルゴリズムにも挑戦してみましょう！
