【基本情報技術者試験平成17年秋期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成17年秋期基本情報技術者午前問14

問14　　 ２分探索に関する記述

　２分探索に関する記述のうち，適切なものはどれか。

ア　２分探索するデータ列は整列されている必要がある。

イ　２分探索は線形探索より常に速く探索できる。

ウ　２分探索は探索をデータ列の先頭から開始する。

エ　 n 個のデータの探索に要する比較回数は， n log₂ n に比例する。

解説

２分探索は、整列されているデータの全体の要素を半分に分け、探索するキーが入っている可能性のある半分について探索を行う。ｎ個の要素を探索する場合、平均比較回数は、「log₂n 」である。

探索するデータが最初の方にある場合は、線形探索の方が速い場合がある。