ITパスポート 令和5年度 問69：algorithmに関する問題

答えは b です。

線形探索は「最初から1個ずつ順番に見ていく」シンプルな探し方。たとえば本棚を端から1冊ずつ確認する感じです。だから本（データ）が増えれば増えるほど、調べる手間もそのぶん増えます。これが「要素数に比例する」という意味です。

👉 覚え方：「線形＝1個ずつ・データが2倍なら手間も約2倍」。

ほかの選択肢：a＝2分探索なのに“先頭から順”は線形探索の説明で×／c＝順番に並んでなくても線形探索はできるので×／d＝2分探索が必ず速いとは限らない（最初の1個が当たりなら線形が速い）ので×。

なぜこれが正解か

正解は b。線形探索は先頭から順に1つずつ比較するため、最悪・平均の比較回数が要素数nに比例する（計算量O(n)）。これは正しい記述。

各選択肢の解説

• a：「先頭から順に探索する」のは線形探索の説明。2分探索は中央値と比較して範囲を半分ずつ絞る方式なので誤り。
• c：ソート（昇順・降順整列）が必要なのは2分探索。線形探索は未整列でも使えるため誤り。
• d：2分探索が常に少ないとは限らない。探す値が先頭付近にある場合は線形探索の方が速いこともあり、「探索する値によらず必ず少ない」は誤り。

覚え方・ひっかけ注意

「線形＝順番にO(n)・整列不要」「2分＝半分ずつO(log n)・整列必須」。前提条件（整列の要否）と「必ず／常に」という断定語がひっかけの定番。

理論的背景

探索アルゴリズムは「データ集合の中から目的の値を見つける手続き」であり、計算量（Time Complexity）によってアルゴリズムの効率性が評価される。本問は線形探索と2分探索の特性比較を問うており、選択肢bの「線形探索法の計算量が要素数nに比例する（O(n)）」が正しい記述である。

線形探索法（Linear Search・Sequential Search）：配列の先頭から末尾に向かって要素を1つずつ順番に比較していく探索方法。ソートの有無に関わらず適用できる。最良ケースはO(1)（最初の要素が目標値）、最悪・平均ケースはO(n)（末尾または存在しない場合）。「計算量が要素数nに比例する」という記述は平均・最悪ケースの計算量を表しており正しい。

2分探索法（Binary Search）：ソート済みの配列を前提として、探索範囲の中央値と目標値を比較し、中央値より大きければ右半分、小さければ左半分に探索範囲を絞り込んでいく手法。各比較で探索範囲が半分になるため、最悪ケースでO(log₂n)の計算量を達成する。例えばn=1024の場合、最大10回の比較で探索完了（2^10=1024）。

各選択肢の詳細検証

選択肢a（「2分探索法は配列の先頭から順に探索する」）が誤りの理由：2分探索法は「先頭から順に」ではなく「常に中央値から始めて範囲を半分に絞り込む」という探索戦略を取る。「先頭から順に」は線形探索法の特徴の説明であり、2分探索の正確な記述ではない。

選択肢b（「線形探索法の計算量は要素数に比例する」）が正しい理由：前述の通りO(n)の説明として正確。

選択肢c（「線形探索法にはソート済み配列が必要」）が誤りの理由：線形探索法の最大の特長はソート不要で任意の配列に適用できる点である。ソート前提が必要なのは2分探索法の方であり、線形探索とソート要件の対応関係が逆になった典型的な誤答パターン。

選択肢d（「同一配列なら探索値によらず2分探索が線形より少ない計算量」）が誤りの理由：「探索する値によらず」という部分が誤り。例えば探索値がたまたま配列の先頭にある場合、線形探索は1回の比較で完了（O(1)のベストケース）するが、2分探索は中央→右or左...という最低でもO(log n)のステップを要する（最初の比較で正解を見つけてもハンドシェイクが必要）。ベストケースでは線形探索の方が少ない比較回数になり得る。

実務での使われ方

アルゴリズムの計算量の実感を持つために具体的な数字で考えると：要素数1,000,000（百万）の配列での最悪探索回数は、線形探索で100万回、2分探索でlog₂(1,000,000)≒20回となる。この約5万倍の差が検索エンジン・データベースインデックス・金融リアルタイム処理において本質的な性能差を生む。

実務では配列の単純な探索より高度なデータ構造が使われる。ハッシュテーブル（Hash Table）はO(1)の平均計算量で値を検索でき、ほぼすべてのプログラミング言語の辞書型・連想配列がこれを基盤とする。B木（B-tree）はデータベースのインデックス実装として広く使われ、O(log n)でのデータ検索・挿入・削除を保証しつつディスクI/O回数を最小化する設計を持つ。全文検索エンジン（Elasticsearch・Apache Solr）は転置インデックス（Inverted Index）を使い、テキストの全文検索をO(1)〜O(log n)で実現する。

試験での位置づけ

ITパスポートのテクノロジ系・アルゴリズム分野では、線形探索・2分探索の特性比較が毎回出題される基本問題である。「2分探索の前提条件（ソート済み）」と「計算量の比較（2分探索はO(log n)・線形探索はO(n)）」という2点を確実に押さえることが最低限の対策。本問の各選択肢は「2分探索と線形探索の特性を入れ替える・特殊ケースを一般化する」という典型的なひっかけ設計であるため、各アルゴリズムの「前提条件」と「計算量」の正確な対応表を持つことが重要。

基本情報技術者試験ではハッシュ法（Hash法）・B木探索・二分木探索も出題範囲となり、各探索アルゴリズムの計算量（最良・平均・最悪）の比較、具体的なアルゴリズムのトレース（中間値を求めてどのステップで目標値が見つかるか）まで問われる。

選択肢の発展補足

2分探索の「ソート前提」がなぜ必要か：2分探索の「中央値と比較して右or左を選ぶ」という戦略が成立するためには、「中央値より大きい値はすべて右側に存在する（または小さい値はすべて左側）」という大小関係による配置が保証されている必要がある。ソートされていない配列では中央値との大小比較が探索範囲の絞り込みの根拠にならないため、2分探索を適用できない。

線形探索が有用な場面：（1）データ量が少ない場合（n<50程度ではO(n)とO(log n)の差は無視できる）、（2）ソートコストが探索コストより高い場合（1回だけ探索して以後は使わない場合、O(n log n)でソートしてO(log n)で探索するよりO(n)で探索する方が総合コストが低い）、（3）データが変動して再ソートが頻繁に必要な場合、（4）実装の簡単さが優先される場合（組込みシステム・コードサイズ制約）に線形探索が実際に採用される。