検索手法

検索手法は、配列、ファイル、表、索引などから条件に合うデータを見つける方法です。データの並び、更新頻度、件数、検索条件に応じて、比較回数、記憶量、前処理コストを選びます。

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

• 線形探索は先頭から順に比較し、未整列でも使えますがn件で平均・最悪$O(n)$です。小規模又は一度だけの検索には単純さが利点です。

• 二分探索は整列済み配列の中央と比較して探索範囲を半分ずつ狭め、$O(\log n)$です。途中要素へ直接アクセスできることと整列維持が前提です。

• ハッシュ探索はキーから格納位置を計算し、適切なら平均$O(1)$ですが衝突処理が必要で、範囲検索や順序付き走査には向きません。

• B木などの索引は検索を高速化し、範囲検索にも使えますが、索引容量と追加・更新時の保守コストが増えます。検索速度だけで方式を決めません。

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

二分探索には整列とランダムアクセスが必要、ハッシュには衝突がある、線形探索は未整列でも可能という前提を見分けます。

例: 1,024件の整列配列を二分探索すると、最悪でも概ね$\log_2 1{,}024=10$回程度の絞込みです。線形探索では最悪1,024件を比較します。