うごく基本情報

平成26年度 秋期 問6

アルゴリズムとプログラミング › 探索アルゴリズム △ ときどき出る

出典:平成26年度 秋期 基本情報技術者試験 午前 問6 の問題

出典:平成26年度 秋期 基本情報技術者試験 午前 問6

正解と解説を見る

正解:ア

覚えること:2分探索=データが整列されていることが前提。真ん中と比べて、範囲を半分ずつに絞る。比較回数は log₂n に比例。

2分探索は、データ列が整列されていなければ使えません(ア)。探索は中央から始めます(ウは誤り)。データ数が少ないときや、目的のデータが先頭にあるときは線形探索の方が速いこともあります(イは誤り)。比較回数は log₂n に比例します。エは誤りです。n log₂n は整列(クイックソートなど)の比較回数の目安で、2分探索の比較回数は log₂n に比例します。

解説はこのサイトが作成したものです。