線形探索法・二分探索法・ハッシュ探索法とは？
線形探索法・二分探索法・ハッシュ探索法とは、データの中から目的の値を見つける代表的な3手法。線形探索は先頭から順に比較（計算量O(n)）、二分探索は整列済みデータの中央値と比較して範囲を半分ずつに絞る（計算量O(log n)）、ハッシュ探索はハッシュ関数でキーから格納位置を直接計算する（計算量は理想的にO(1)）。
応用情報技術者試験の過去問では1回出題されています。
せんけいたんさくほう・にぶんたんさくほう・はっしゅたんさくほう
線形探索法・二分探索法・ハッシュ探索法の意味
データの中から目的の値を見つける代表的な3手法。線形探索は先頭から順に比較（計算量O(n)）、二分探索は整列済みデータの中央値と比較して範囲を半分ずつに絞る（計算量O(log n)）、ハッシュ探索はハッシュ関数でキーから格納位置を直接計算する（計算量は理想的にO(1)）。
線形探索法・二分探索法・ハッシュ探索法の具体例
1024件の整列済みデータを二分探索すると最大でも10回程度（log₂1024＝10）の比較で見つかる。ハッシュ探索は電話番号を格納する配列の添字をハッシュ関数で直接求めるイメージで、衝突（同じ格納位置になること）が起きた場合はチェイン法やオープンアドレス法で対処する。
線形探索法・二分探索法・ハッシュ探索法は試験でどう引っ掛けられる？
二分探索を使うにはデータが事前に整列されている必要がある。未整列のまま適用すると正しい結果が得られない。
線形探索法・二分探索法・ハッシュ探索法と関連する用語
線形探索法・二分探索法・ハッシュ探索法が出た過去問
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、…
正解：(n+1)(1-a)/2 + na
要点：線形探索の平均比較回数は、成功時(n+1)/2・失敗時n
表に存在する場合（確率1-a）は、目的の要素が先頭からn番目までのどこかに等確率であるので平均比較回数は(n+1)/2になる。存在しない場合（確率a）は末尾まで調べ切るのでn回である。両者を確率で重み付けして足すと(n+1)(1-a)/2 + na となる。
出典：令和5年度 春期 応用情報技術者試験 午前 問6（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。