アルゴリズム（リニアサーチ）

今回はアルゴリズムの中におけるリニアサーチについて述べたいと思います。なお、この記事を書いた後、もっとよいプログラムの書き方を見つけて追加記事を書いています。

こちら

前回リニアサーチについて記事にしましたが、その後、リニアサーチについていろいろ考えていたところ、もっといいやり方があることに気付きました。そんなわけで続き記事として記載しています。 Scrachのリニアサーチ修正版プログラム Scrat...

サーチプログラムとは
リニアサーチ（線形探索）とは
フローチャートを書く
プログラムを書く
1. Scratchで書く
2. Pythonで書く
まとめ

サーチプログラムとは

サーチプログラムとは、その名のとおり「サーチ（探す）」ためのプログラムです。沢山あるデータの中から、目的のものを探すためのプログラムのことになります。

サーチプログラムを実現するためのアルゴリズムには代表的なものとして「リニアサーチ（線形探索）」と「バイナリサーチ（二分探索法）」というものがあります。

リニアサーチ（線形探索）とは

さてリニアサーチとはどんなものなのか、これはサーチプログラムにおいては一番シンプルなものであり、単純に探したい数を、対象のデータの先頭から順番に数えていくというものです。

これは単純なのですが、１つ１つ探していくので、探したい値が探す対象の一番最後の方にあったら、それこそとても時間がかかります。この探す時間がかかるというのを、より短縮するための探索法がバイナリサーチなのですが、これは、また次の機会に説明したいとおもいます。

ここでイメージ図です。

探す対象データを配列 A[ ]に格納。探す数を変数s、反復処理で使うカウンタとして変数 i、探した結果を格納するための変数をresultとします。その上で、このリニアサーチの探索方法をイメージすると以下となります。

なお、ここでは表現していませんが、resultの初期値には-1を入れることにします。これは、配列の中を全て調べても探したい数が見つからなかったときに、みつからなかったよと表現するための値として準備しています。

フローチャートを書く

さてリニアサーチについてフローチャートで表現してみます。

このフローを説明すると変数についてはイメージ図で説明した通りで、反復処理においてカウンタを配列の長さまで回して、その中で探す数sと変数のi番目の値を比較して、一致しなければカウンタを１追加して反復処理を継続、一致したらresultの値を見つけた値で更新して、反復処理を抜けます（break）。最後の部分はリニアサーチとは直接かかわりませんが、resultの値が-1なら、つまり探す数がみつからずresultの値が一度も更新されてない状態ならば「見つかりませんでした」と出力、値が-1以外であったら「見つかりました」と出力させています。

プログラムを書く

ではいつものようにプログラムを書いていきましょう。

Scratchで書く

Scrachで書いていきます。

・・・が、以下のPythonで書く場合はわかるのですがScratchで書くと意外と難しいですね。そんなわけで、前回紹介したプログラムアルゴリズムの図鑑も参考にして書いてみましたが・・・あれ、動かない。不等号とか設定とか変えてみてやっと動いたけど、探索されない数をセットするとループが永遠に続く。あれー、テキスト間違ってないか？とおもって正誤表みたら、確かに修正されてた。でも、その修正版でも反復処理が配列の長さ分すべて実施するとなっていて、これだと探索数が多くなるなぁと思われ・・・

そんなわけで、Scratchでbreakに相当するものを探し出して作り直した完全に動くバージョンはこちらです。

共有はこちら

https://scratch.mit.edu/projects/338292004/

結局のところ、このプログラムではScratchで反復を抜けるbreakに相当するものがないため、代わりに「メッセージを送る」と「このスクリプトを止める」で実現しています。この回になって、プログラミングの勉強である程度進むと、実はScrathで実現するには、逆に難しいケースもでるんじゃないかと、初めておもったりしちゃいました。

ちなみに不完全であったプログラムも一応載せておきます。探索する数があるときは正常に動きますが、探索する数がない時は永遠にループしてしまいます。多分、反復条件の-1 < result を満たすことがないからかと。

https://scratch.mit.edu/projects/338499317/

Pythonで書く

Pythonで書いていきます

<span style="font-size: 16px;">print("探す正の数は何？")
s = int(input())
A = [5,9,7,4,2,1,6,8,3]
i = 0
result = -1
for i in range(len(A)):
if s == A[i]:
result = A[i]
break
else:</span>　　　　　<span style="font-size: 16px;"><span style="font-size: 14px;">#</span></span><span style="font-size: 14px;">このelseとi+=1はなくても動くけどフローにあわせるため明示的に記載</span><span style="font-size: 16px;">
i+=1 </span><span style="font-size: 16px;">
if result != -1:
print("探す数"+str(s)+"は配列Aの"+str(i+1)+"番目にあったよ")
else:
print("探す数"+str(s)+"はみつからなかったよ") 
</span>

<spanstyle="font-size: 16px;">print("探す正の数は何？")

s=int(input())

A=[5,9,7,4,2,1,6,8,3]

i=0

result=-1

foriinrange(len(A)):

ifs==A[i]:

result=A[i]

break

else:　　　　　<spanstyle="font-size: 16px;"><spanstyle="font-size: 14px;">#このelseとi+=1はなくても動くけどフローにあわせるため明示的に記載

i+=1<spanstyle="font-size: 16px;">

ifresult!=-1:

print("探す数"+str(s)+"は配列Aの"+str(i+1)+"番目にあったよ")

else:

print("探す数"+str(s)+"はみつからなかったよ")

さて解説していきます。今回はちゃんとどの数を探すときいてその値を、探す対象の配列からさがすようにinput( )関数を用いていますが、入力した数を整数のデータ型で扱うためint( )関数で型変換しているので、s=int( input( ) )となっています。

その後、フローチャートでも書いたとおりの変数を定義

その後が反復処理（ループ）で配列の長さ分、ループ処理を行います。そのループ処理の中で条件分岐を使い、探す数 s と配列の中の値A[ i ]が一致した場合、result変数に配列の値A [ i ]をいれてループをぬけるbreak処理。そうでない場合は、カウンタiをプラスしてループに戻ります。

最後にprintで結果出力です。resultが初期値の -1 のままであれば探す数が見つからなかったと表示、-1 以外の場合は探す数が見つかったのでresultの値と配列の何番目にあったかを表示します。なお、print関数の中では文字列で扱うため、変数 result と i はstr( )で文字列型に変換しています。またデータの配列は 0 からスタートするため、+1 して人間の感覚に合わせるように修正しています。