アルゴリズム・データ構造 プログラミング

[アルゴリズム(Ruby)]線形探索法(リニアサーチ)の解説

アルゴリズム解説_線形探索法

線形探索法(linear search)とは

線形探索法(linear search)は、沢山のデータを一直線に並べて先頭(又は末尾)から順番に調べて、特定のデータを見つけ出すアルゴリズムです。
結果を記録する変数を用意してデータを順番に調べていき、特定のデータがあれば結果の変数を更新する流れで実装出来ます。

イメージとしてはシャッフルされたトランプの山があって、その中から特定のカードを探すために上から1枚ずつめくっていくような感じになります。

特定の値が有るか無いかを調べる

問題

データ数 n=10配列 a=[5, 2, 3, 6, 1, 9, 7, 4, 6, 5]の中に、対象の値 k=6有るか無いかを調べる。

処理の流れ
  • 探索結果をresult=falseで初期化する
  • 配列 aの先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx]==k(6)trueならresult = trueで更新する
    • breakでループから抜ける
      (有無の確認なので、見つかった時点でその後の探索は不要)
  • 探索結果resultを確認する(trueなら有り / falseなら無し)

線形探索01

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx]==k(6)trueならresult += 1で更新する
  • 探索結果resultを確認する

線形探索02

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx]==k(6)trueならresult = idxで更新する
    • breakでループから抜ける
      (ループを抜けないとk(6)が複数あった場合、resultを上書きしてしまう)
  • 探索結果resultを確認する

線形探索03-01

サンプルコード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の末尾から順に参照するループを設定する
    (添字 idx9(n - 1) から 0の間でカウントダウンしてa[idx]を参照)

    • もしa[idx]==k(6)trueならresult = idxで更新する
    • breakでループから抜ける
      (ループを抜けないとk(6)が複数あった場合、resultを上書きしてしまう)
  • 探索結果resultを確認する

線形探索03-02

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx]==k(6)trueならresultidxを追加する
  • 探索結果resultを確認する

線形探索03-03

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx] < min_numならmin_num = a[idx]で更新する
  • 探索結果min_numを確認する

線形探索04-01

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx] > max_numならmax_num = a[idx]で更新する
  • 探索結果max_numを確認する

線形探索04-02

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 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を確認する

線形探索04-03

サンプルコード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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx] < min_evenかつa[idx]%2==0ならmin_even= a[idx]で更新する
  • 探索結果min_evenを確認する

線形探索05-01

サンプルコード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を行うのでサンプル1・2より処理が遅いです。

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の先頭から順に参照するループを設定する
    (添字 idx0 から 9(n - 1)の間でカウントアップしてa[idx]を参照)

    • もしa[idx] > max_oddかつa[idx]%2!=0ならmax_odd=a[idx]で更新する
  • 探索結果max_oddを確認する

線形探索05-02

サンプルコード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を行うのでサンプル1・2より処理が遅いです。

n = 10
a = [5, 2, 3, 6, 1, 9, 7, 4, 6, 5]

p a.select { |num| num.odd? }.max
# > 9

今回のまとめ

線形探索法の手順

  • 結果記録用の変数を準備して適切な値で初期化する
  • 繰り返し処理でデータの探索を行い、条件分岐で結果記録用の変数を上書きする
  • 必要に応じてループを抜ける処理を入れる
  • ループを抜けた後、結果記録用の変数を確認する

複数条件の探索

  • 繰り返し中の条件をアンド(&&)で繋げば複数条件に対応できる
  • メソッドを繋げると(メソッドチェーン)スッキリ書けるが処理速度は遅くなる

線形探索は流れが単純なので実装しやすいですが、要素数が大量になると探索に時間がかかるという弱点もあります。
線形探索に慣れてきたら他の探索アルゴリズムにも挑戦してみましょう!

おすすめアウトプット【広告】


paizaに無料登録して動画教材(一部有料)や、練習問題・スキルチェック問題を解いてさらにレベルアップしましょう!
また、あなたのプログラミングスキルが数値化され、(希望があれば)企業からのオファーが届くので、理解度確認&転職活動にオススメです!


スキルテストで自分の市場価値がわかる【paiza】



Ruby学習でお世話になった本




【PR】アルゴリズム学習でお世話になった本


アルゴリズム関連の技術書は大抵C/C++で書かれていますが、ある程度プログラムが出来れば、処理の流れは理解することが出来ます。






通称: 螺旋本。C++で解説されています。AOJ(Aizu Online Judge)を運営している会津大学の渡辺准教授が書いた本です。データ構造や計算量の内容から丁寧に書いてありますのでアルゴリズム学習の最初の参考書としてオススメです。







通称: 蟻本。C++で解説されています。競技プログラミング中級者の定番書と言われていて、競技プログラミングで利用できる色々なアルゴリズムを学ぶことが出来ます。かなり高度な内容も含まれているので1冊分を完全に理解するのにはかなりの時間がかかりそうですが、手元に置いて何度も読み返しています。







通称: チーター本。C#, C++, JAVAでTopcoderの問題を解説しています。初心者~中級者向けに書かれているので解説が非常に丁寧です。







Python3でアルゴリズムを解説している本です。講義スタイルの本で、図やフローチャートを使ってアルゴリズムとデータ構造についてしっかりと説明されています。代わりにコードは少なめです。Pythonコードが読めなくても十分理解できると思います。


-アルゴリズム・データ構造, プログラミング
-

© 2024 じゃいごテック