IT PASSPORT
ITパスポートの問題解説
問題
配列に格納された多数のデータの中から目的の値を探す。データが整列されているかどうかに関係なく使え、先頭から末尾へ向かって1件ずつ順に比較していく探索方法はどれか。
- ア 線形探索
- イ 二分探索
- ウ 選択ソート
- エ 挿入ソート
出典：オリジナル問題｜参考範囲：IPA ITパスポート試験シラバス（最新版）、情報処理技術者試験の基礎知識
正解と解説
正解：線形探索
解説：線形探索はデータが整列していなくても使える最も素朴な探索方法で、見つかるまで（または最後まで）順に比較します。目的の値が偶然先頭にあれば1回で済みますが、末尾にあれば全件を、存在しなければ全件を調べて初めて「無い」と判断でき、件数に比例して比較回数が増える（計算量O(n)）のが弱点です。混同しやすい二分探索は整列済みであることが前提で、毎回範囲を半分に絞れる代わりに未整列データには使えません。選択肢の選択ソートや挿入ソートは「並べ替える」整列方法であって、「探す」探索方法ではない点が大きな違いです。「探索」と「整列」は目的そのものが異なるため、まず操作の種類を見極めることが正答への近道です。
覚え方：「順番に総当たり＝線形探索」「整列が前提＝二分探索」。さらに『ソート』が付く語は並べ替え（整列）で探索ではない、と分類してから選ぶと迷いません。
他の選択肢はなぜ違う？
- イ二分探索はあらかじめ整列済みのデータに対し中央の値と比較して範囲を半分ずつ絞る探索方法です。整列を前提とする点で、整列の有無を問わない本問とは条件が異なります。
- ウ選択ソートは未整列部分から最小（または最大）の値を選んで先頭へ移すことを繰り返す整列方法であり、目的の値を探す探索方法ではありません。
- エ挿入ソートは整列済みの並びに、新しい要素を正しい位置へ差し込みながら並べ替える整列方法であり、探索方法ではありません。
この問題について
IPAのITパスポート試験シラバスとIT基礎知識を参考に、Sikaku Master向けに独自作成した問題です。公式試験問題・過去問題の転載ではありません。
IPAの過去問題の転載ではなく、シラバス・公開情報に基づく独自問題として作成しています。