問69の正解: イテクノロジ系／基礎理論
配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述のうち、適切なものはどれか。
この設問が問うていること
線形探索法と2分探索法の仕組みや計算量、前提条件の違いについて問う設問です。
ア2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
選択肢アの解説: 先頭から順番にチェックしていくのは、2分探索法ではなく「線形探索法（リニアサーチ）」の特徴です。
イ線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。正解
選択肢イの解説: 線形探索法では要素数が増えるほど比較回数も正比例して増える（最悪計算量がO(N)となる）ため、記述は適切です。
ウ線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
選択肢ウの解説: 要素がソート（整列）されている必要があるのは、2分探索法であり、線形探索法はソートされていなくても適用可能です。
エ探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。
選択肢エの解説: 探索する値や位置によっては、1回目の比較で先頭で見つかる線形探索法の方が計算量が少なくなる場合もあります。
総合解説
探索アルゴリズム（線形探索と2分探索）の特徴に関する設問です。 ・線形探索法（リニアサーチ）は、配列の先頭から順に調べる手法で、要素数 N に対して平均 N/2 回、最悪 N 回比較するため、必要な計算量は要素数に比例（O(N)）します。よって、bが適切です。 ・2分探索法（バイナリサーチ）は、中央のデータと比較して探索範囲を半分に絞り込んでいくため、配列データがソート（昇順または降順に並んでいる）されている必要があります（cは線形探索と2分探索の条件が逆になっており誤り）。 ・2分探索は最悪でも O(log N) の計算量で済みますが、探索するデータが配列の先頭にある場合など、特定の場合には線形探索の方が比較回数が少なくなります（dは誤り）。また、aは線形探索の説明です。したがって、正解はbです。
AIAIにその場で質問（デモ応答）
こんな聞き方もできます（タップで質問）