線形探索の実装と理解

「この値、リストのどこにあるんだろう？」そんなときにまず試してみたいのが、線形探索（Linear Search）です。 Python初心者でもすぐに使える、シンプルで直感的な探索アルゴリズムを、実装から使い方、考え方までやさしく解説します。

アルゴリズムとは？なぜ学ぶのか

まずは、アルゴリズムについて解説します。

いきなり“アルゴリズム”と聞くと、専門的で取っつきにくいと感じませんか？アルゴリズムとは、問題を解決するための手順や考え方のこと。料理のレシピや、駅までの行き方のメモのように、決まった順番で作業すれば、誰がやっても同じ結果にたどり着ける「再現性のある手順」です。

では、なぜPython初心者やIT初心者がアルゴリズムを学ぶ必要があるのでしょうか?

理由はいくつかあります。まず、同じ結果を出すプログラムでも、やり方によって「速さ」や「メモリの使い方」が大きく変わります。データが増えるほど、その差はどんどん広がります。さらに、アルゴリズムを学ぶと、コードが整理され、バグも減りやすくなります。もし「処理が遅い」「どこから手を付けていいかわからない」と感じた経験があるなら、アルゴリズムを理解することで一気に視界がクリアになります。

今回は、最も基本的でシンプルな探索アルゴリズムである「線形探索（Linear Search）」を丁寧に解説します。

線形探索とは？直感でわかる基本の考え方

はじめに、線形探索のイメージをつかみましょう。線形探索は、リストや配列の先頭から1つずつ順番に見ていき、探している値（ターゲット）が見つかったらそこで止める方法です。

辞書を最初のページからめくって目的の言葉を探すイメージに近いですね。

最悪の場合はリストの最後まで全部調べる必要があるため、かかる時間は要素数に比例します。これを時間計算量と呼び、線形探索は O(n) と表現します。「O(n)」は、新しい用語に見えるかもしれませんが、「データが2倍になれば、だいたい処理時間も2倍になる」くらいのイメージがあれば十分です。

たとえば次のリストから数値 5 を探したいとします。

numbers = [1, 3, 5, 7, 9]

先頭の 1、次に 3、そして 5…という順番で照らし合わせていき、5に一致したところで探索は終了です。「見つけたら止まる」というのがポイントです。

Pythonで書く線形探索

では、Pythonで線形探索を実装してみましょう。まずは最もベーシックな書き方です。初めてでも読みやすいように、関数の目的と返り値を文書化しつつ進めます。

def linear_search(lst, target):
    """
    線形探索でリスト内からターゲットを探す関数

    :param lst: 探索対象のリスト
    :param target: 探したい値
    :return: 見つかったらそのインデックス、見つからなければ -1
    """
    for index in range(len(lst)):
        if lst[index] == target:
            return index  # 見つかったら位置（インデックス）を返す
    return -1  # 最後まで見つからなければ -1

この関数は、先頭から順に要素を取り出して、ターゲットと「等しいかどうか」をチェックします。一致した瞬間にインデックスを返し、処理を終了します。最後まで一致しなければ、見つからなかったことを示す -1 を返します。つまり、戻り値が -1 かどうかを見れば、存在したかどうかが一目でわかります。

次に、実際に関数を呼び出して、結果を表示してみます。

# 上記コードの続き
numbers = [1, 3, 5, 7, 9]
target = 5

result = linear_search(numbers, target)

if result != -1:
    print(f"ターゲットの{target}は、インデックス{result}に存在します。")
else:
    print(f"ターゲットの{target}はリスト内に存在しません。")

このコードを実行すると、次のように表示されます。

ターゲットの5は、インデックス2に存在します。

なぜインデックスが 2 なのか不思議に思った方は、Pythonが 0 から数える点を思い出してください。numbers[0] が 1、numbers[1] が 3、numbers[2] が 5 です。

計算量と使いどころ

線形探索の計算量は、O(n) です。

といっても、いきなり数式のように見えるこの表記を難しく考える必要はありません。 ここでの「O(n)」とは、「データの数が2倍になれば、処理時間もだいたい2倍になる」くらいのシンプルな意味です。 つまり、データ量に比例して処理が増えるということですね。

線形探索の計算量をもう少し詳しく

線形探索は、リストの要素を1つずつ順に調べる仕組みです。 たとえば100個のデータがあれば最大で100回、1000個なら最大で1000回チェックします。

これをもう少し分解して考えると次のようになります。

最良のときは速いけど、運が悪いと全部見る必要があるというのが、線形探索の特徴です。 このように、最悪の場合でも確実に動くが、データが増えるほど処理が重くなるというバランスがポイントです。

空間計算量（メモリの使い方）

空間計算量とは、どれくらいのメモリを使うかということです。

線形探索は、リストをそのまま使って探索するだけなので、特別なメモリを必要としません。したがって、空間計算量は O(1)（定数時間）です。

つまり、「どれだけデータが増えても、使うメモリ量はほぼ変わらない」という意味です。

どんなときに線形探索を使えばいいの？

上記の計算量を踏まえて、どのような場面で線形探索を使えば良いのでしょうか？ 向いている場面と不向きな場面を解説します。

向いている場面

たとえば、以下のようなケースでは線形探索が最適です。

• データが少ない（10件、100件程度）→ 探索時間はほとんど気にならない。
• リストがソートされていない（順番バラバラ） → どのみち順番がないなら、先頭から見るのが一番シンプル。
• とりあえず動くものを作りたいとき → 実装が簡単でバグも少ない。学習用や試作品にもぴったり。

避けたほうがいい場面

一方で、線形探索が効率面で不利になる場面もあります。

• データ量が非常に多い（数万〜数百万件） → 1件あたりの処理が増えて、時間がかかる。
• 同じ検索を何度も繰り返す → そのたびにリスト全体を見直す必要があり、非効率。
• データがすでにソートされている → この場合は次に学ぶ「二分探索（O(log n))」の方が圧倒的に速い。
• 高速検索が重要なアプリケーション → set や dict（ハッシュテーブル）を使う方がベター。

線形探索の特徴を理解して、どのような場面で使うべきはを理解しておきましょう！

まとめと次のステップ

ここまで、線形探索（Linear Search）の基本概念、Pythonでの実装、使い方、現場での応用、計算量の考え方まで一通り学びました。線形探索は「まず動く解」を素早く作るのに最適で、データが小さい場面では十分に実用的です。逆にデータが大きい場合や、繰り返し検索が必要な場合は、より効率的な方法を選ぶのが賢い判断です。

次のステップとして、ソート済みのリストに対して劇的に速くなる「二分探索の実装と応用」を学びましょう。線形探索との違いを知ることで、「どの場面でどの探索を選ぶか」というエンジニアの設計力が身につきます。