[基本情報技術者試験]線形探索のアルゴリズムをPythonで書いてみた。

概要

• 基本情報技術者試験の午後の試験でアルゴリズムがあります。過去問を解いても理解ができません…。実際にアルゴリズムをPythonで書いて、理解を深めていきたいと思います。

• 前回は配列の最大値のアルゴリズムを書きました。

• 今回は線形探索のアルゴリズムから書いてみます。

線形探索

アルゴリズム

• 配列の要素を先頭から末尾まで順番に取り出して、指定された値と比較する。

コード

# 線形探索で指定された値を見つけるSeqSearch関数
def SeqSearch(A,Length,X):
    Pos = -1
    i = 0
    # 繰り返し処理
    while i < Length and Pos == -1: # 「配列の末尾に達していない」と「見つかっていない」を意味する
        print("Pos=",Pos,"i=",i,"A[i]=",A[i]) # 途中の結果
        # 分岐処理
        if A[i] == X:
            Pos = i
        i += 1
    return Pos

print("実行結果：",SeqSearch([22,55,66,11,44,77,33],7,77))

実行結果

Pos= -1 i= 0 A[i]= 22
Pos= -1 i= 1 A[i]= 55
Pos= -1 i= 2 A[i]= 66
Pos= -1 i= 3 A[i]= 11
Pos= -1 i= 4 A[i]= 44
Pos= -1 i= 5 A[i]= 77
実行結果： 5

まとめ

• 線形探索はちょっと複雑
• 次回は二分探索のアルゴリズムを書こうかな

参考

• こちらの本のCHAPTER3 04線形探索を引用または参考にしました。
  情報処理教科書 基本情報技術者試験のアルゴリズム問題がちゃんと解ける本 第2版