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

探索アルゴリズムは、データ集合から目的のキー・条件を満たす要素を見つける手順で、データ構造と事前条件により時間・記憶量が異なります。

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

• 線形探索は先頭から順に比較し、未整列データにも使え、最悪時間は$O(n)$です。

• 2分探索は整列済み配列の中央で候補を半分にし、最悪時間は$O(\log n)$ですが整列とランダムアクセスが前提です。

• ハッシュ探索はキーから格納位置を計算し平均$O(1)$を期待できますが、衝突処理と適切な表サイズ・ハッシュ関数が必要です。

• 木・グラフでは深さ優先探索と幅優先探索を使い、重みなしグラフの最短辺数は幅優先探索で求められます。

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

未整列なら線形、整列済み配列なら2分、完全一致キーを頻繁に引くならハッシュが候補です。アルゴリズムの前提条件と計算量を一緒に選びます。

例: 100万件の整列済み配列なら2分探索は比較回数が約20回ですが、線形探索は最悪100万回です。