令和5年度 ITパスポート試験 公開問題 問69 解説 探索アルゴリズム

この問題は、探索アルゴリズムの代表格である「線形探索法」と「2分探索法」の仕組みと効率性を理解しているかを問うものです。正解を導くには、それぞれのアルゴリズムが「どのような手順で探すのか」という特性を比較することが重要です。

線形探索法と2分探索法の特徴

線形探索法（リニアサーチ）は、配列の先頭から順番に目的の値を探していく方法です。1番目のデータが違うなら2番目、というように順次確認するため、最悪の場合、すべての要素を調べることになります。要素数が$n$個ある場合、比較回数は最大で$n$回となります。この「要素数に比例して計算量が増える」という性質が、この選択肢の正解根拠です。

2分探索法（バイナリサーチ）は、あらかじめ値が昇順または降順に並んでいるデータに対して有効な手法です。配列の真ん中の値と目的の値を比較し、目的の値がそれより大きいか小さいかによって、探索範囲を半分に絞り込んでいきます。これを繰り返すことで、非常に効率よく探せます。

各選択肢の解説

線形探索法は先頭から順に調べる手法であり、ソート（整列）されている必要はありません。一方で、2分探索法は範囲を絞り込む性質上、必ず事前にソートされている必要があります。

探索に必要な計算量については、確かに2分探索法の方が一般的には高速です。しかし「探索する値」によって計算回数が変わる場合があります。例えば、探索したい値が配列のちょうど中央にある場合、2分探索法なら1回の比較で見つかりますが、線形探索法でもたまたま先頭にあれば早くなります。つまり、探索する値や配列の並び順によって状況は異なるため、「2分探索法が常に線形探索法よりも少ない計算量で済む」とは言い切れません。また、データがソートされていない場合、2分探索法を使うためにソートというコスト（計算量）が発生することも忘れてはいけません。

試験での活用ポイント

ITパスポート試験では、アルゴリズムの仕組みだけでなく「前提条件」もよく問われます。以下の表のようなイメージを持って整理しておくと混乱しません。

線形探索法：

• 条件：特になし
• 手順：先頭から順番に確認
• 計算量：要素数に比例する

2分探索法：

• 条件：データがソート済みであること
• 手順：真ん中を確認して範囲を半分に絞る
• 計算量：線形探索より大幅に少ない（対数的な計算量）

実務では、データ件数が少ない場合は実装が簡単な線形探索法で十分なケースが多く、膨大なデータに対して高速な検索が求められる場合には2分探索法や、より高度なインデックス（索引）を用いた探索が活用されます。

• 基本情報技術者講座（線形探索）
• 基本情報技術者講座（2分探索）
• ITパスポート過去問解説（アルゴリズム）