検索手法

検索手法は、配列や表などから、条件に合うデータを見つける方法です。データの並び方や件数に応じて方式を選びます。

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

• 線形探索は先頭から順に比べ、並んでいないデータにも使えます。比較回数はO(n)です。

• 二分探索は整列済みのデータの中央と比べ、範囲を半分ずつ絞ります。比較回数はO(log n)です。

• ハッシュ探索はキーから格納位置を計算するため速いですが、衝突への対処が必要です。

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

二分探索には整列が必要、線形探索は未整列でも使えるという前提を見分けます。

例: 1,024件を二分探索すると、最大でも約10回の比較で見つかります。