アルゴリズム？プログラミング。 - 探そう！線形探索

検索対象のものの中全て総当たりで探す方法。今回は数字がたくさん入っているリストの中から探す数字を一つずつ照らし合わせてもし、探している数字と同じであれば、検索終了。とします。

単純に繰り返し、一つずつ数字を取り出して調べていきます。繰り返しと言えば、for in ループですのでこれを使いコードを書いていきます。

単純にループを使って一つずつ探す方法。

arr = [6,2,1,9,5]

こんなリストがあって、例えば数字の"1"を探します。

探す数字の変数を作ります。探す数字を"1"とします。

serchNum = 1

あとはリストの中の数字を一つずつ取り出して比較して同じかどうか調べます。

一つずつ取り出すのはfor in ループを使います。

for i in arr:

変数そのまま使います。こうすると変数arrの値を一つずつ"i"に入れることができます。そこで、

 if serchNum == i:
        print("見つかった")
　　　　　break

としてif分で探している数字"serchNum"と取り出しあた値"i"が同じかどうか調べます。同じであれば、次の処理"print("見つかった")"が実行されるということです。そして見つかればそこで終わりたいので"break"を入れています。

もし見つからない場合は

else:
     print("none")

ということで実行させます。

全体は、

arr = [6,2,1,9,5]

serchNum = 1

for i in arr:
    if serchNum == i:
        print("見つかった")
        break
else:
     print("none")

あるかないかはこれで結果が出ますが、探している数字がこのリストの何番目にあるかを調べてみます。

arr = [6,2,1,9,5]

serchNum = 2

for i in range(len(arr)):
    if serchNum == arr[i]:
        print("indexは　" + str(i))
        break
else:
     print("none")

インデックスを取るためにここでは、range(len(arr))でリストの長さを調べてその分繰り返します。そしてそのインデックスからリストの数字を示してserchNumの数字と比べます。

 if serchNum == arr[i]:

という感じになります。

あとは一番最初と同じで、正解であればそこで終了。今回は

 print("indexは　" + str(i))

という感じに言葉にしてみました。

以下はwhileを使って線形探索のサンプルを作られています。

Pythonで線形探索法

a = [3,5,7,9,11,13,15,17,19,21,23,25,27]

i=1

m=11

j=len(a)

while (i<=j) and m!=a[i-1]:
    i=i+1
    print(i)

if i<=j:
    print(i)

このコードのポイントは

while (i<=j) and m!=a[i-1]:

"m!=a[i-1]"です。
ここで同じ数字が見つかるとwhileループの条件から外れるのでループを抜けて、そのインデックスを出力するという方法です。