線形探索法とは？せんけいたんさくほう
線形探索法とは、データを先頭から順に1件ずつ比較して目的の値を探す方法。整列されていなくても使え、前処理も追加の記憶領域も要らない代わりに、比較回数は目的の位置に比例し、n件で平均n/2回、最悪n回になる。件数が少ない場合や探索の回数自体が少ない場合には、この単純さが選択理由になる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
2分探索は事前に整列されていること、ハッシュ表探索は表を構築しておくことが前提で、どちらも探索を速くする代わりに準備の費用を先払いしている。同じ集合を何度も引くならその先払いは回収できるが、一度しか探さないなら準備のほうが高くつく。探索アルゴリズムの選択は、計算量の大小ではなく、準備費用を回収できる回数だけ引くのかという判断であり、応用情報はその判断理由を問う。
具体例
1,000件の配列を線形探索すると平均500回、最悪1,000回の比較で済む。2分探索なら最悪でも10回だが、そのために整列が必要で、比較回数はおよそ1万回に及ぶ。1回しか探さないなら線形探索のほうが速く終わる、という逆転がここで起きる。
試験での引っ掛け
平均比較回数をn回と覚える誤りが定番で、正しくは平均およそn/2回、最悪と「見つからなかった」場合がn回。もう一つは配列末尾に探索値を置く番兵法で、これは比較回数そのものを半減させるのではなく、範囲外判定の分岐を消してループ内の比較を1回に減らす工夫である。
関連用語
出た過去問
出典：令和5年度 春期 応用情報技術者試験 午前 問6（IPA）
従業員番号と氏名の対が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 となる。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。