代表的な探索アルゴリズム

探索アルゴリズムは、データの中から目的の値を探す手順です。データが整列されているかどうかなどの前提によって、使える方法と速さが異なります。

■ 試験で押さえるポイント

• 線形探索は先頭から順に比べる方法で、整列していないデータにも使えます。計算量は$O(n)$です。

• 2分探索は整列済みのデータの中央と比べて範囲を半分に絞る方法で、計算量は$O(\log n)$です。

• ハッシュ探索はキーから格納位置を計算するため、平均$O(1)$で探せます。

■ 選択肢での判断ポイント

2分探索はデータが整列済みであることが前提です。前提条件と計算量を合わせて覚えます。

例: 100万件の整列済みデータなら、2分探索は約20回の比較で見つかりますが、線形探索は最悪100万回かかります。