問題
テクノロジ系
問69 配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
選択肢
- ア2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
解説
正解：イ
概要
この問題は、配列のデータを探すときに用いる探索アルゴリズムの特徴と計算量について問うものです。線形探索法と2分探索法の違いを理解しているかがポイントです。
正解の理由
線形探索法は配列の先頭から順に1つずつ調べていく方法であり、最悪の場合は全ての要素を確認します。そのため、必要な計算量は配列の要素数に比例します。よって、この内容を正しく述べているイが正解です。
各選択肢の解説
ア（×）: 先頭から順に探索するのは線形探索法の説明です。2分探索法は中央の要素と比較しながら探索範囲を半分に絞る方法であり、記述が誤っているため不正解です。
イ（〇）: 線形探索法は要素を順番に確認するため、最悪の場合は全要素を調べます。そのため計算量は要素数に比例し、説明として正しいので正解です。
ウ（×）: 配列が昇順や降順にソートされている必要があるのは2分探索法です。線形探索法は並び順に関係なく利用できるため、この記述は誤りです。
エ（×）: 2分探索法は一般に計算量が少なくなりますが、探索する値や要素数によっては必ずしも常に少ないとは限りません。また前提として配列が整列されている必要もあるため誤りです。
ポイント
線形探索法は並び替え不要で計算量は要素数に比例し、2分探索法は整列済み配列で高速に探索できる点を区別して覚えましょう。