[Python] 線形探索

線形探索

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ソートされていないリストが与えられて、その中から、目的の対象を検索することを考えます。

線形探索は、単純に、リストを最初から一つずつ、値が見つかるまで検索します。

リストから該当をするものを1つ探す場合は、時間計算量は \(O(n)\)、空間計算量は \(O(1)\) になります。

import random

def linear_search(lst, target_val):
    for i in range(len(lst)):
        if lst[i] == target_val:
            return i
    return False

def print_serach_result(lst, target_val):
    target_index = linear_search(lst, target_val)
    if target_index:
        print(f'{target_val}は{target_index+1}番目に見つかりました。')
    else:
        print(f'{target_val}はリストの中にありません。')


if __name__ == '__main__':
    # 適当なリストの生成
    random.seed(1)
    lst = [random.randint(1, 100) for _ in range(10)]
    # [18, 73, 98, 9, 33, 16, 64, 98, 58, 61]
    print(lst) 

    # 線形探索
    # 64は7番目に見つかりました。
    print_serach_result(lst, 64)
    # 63はリストの中にありません。
    print_serach_result(lst, 63)

想定通りの結果を得ることができました。