線形探索（番兵法）

はじめに

　順番に全部探索していくということで、「for文で一発やんけ!w」と思って説明を読んでいきました。すると、番兵法というものを見てよくこんなこと思いつくなぁと思いました。

コード

linear_search.py

def linear_search(A,key):
    i = 0
    A.append(key)
    n = len(A) - 1
    while A[i] != key:
        i += 1
    if i == n:
        return "NOT_FOUND"
    return i

説明

　引数に配列Aと探したい値keyを取ります。見つかれば最初に見つかった配列のインデックス、見つからなければNOT_FOUNDという文字列を返します。keyを配列の末尾に追加（番兵）することによって、whileの終了が保障されているため終了条件がいらなくなっています。（なんかすごい）

参考文献

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E6%94%BB%E7%95%A5%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-%E6%B8%A1%E9%83%A8-%E6%9C%89%E9%9A%86/dp/4839952957)