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

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

平成17年春期基本情報技術者午前問15

問15　　 ２分探索の最大探索回数

　２分探索において，データの個数が４倍になると，最大探索回数はどうなるか。

ア　１回増える。　　　　　イ　２回増える。

ウ　約２倍になる。　　　　　エ　約４倍になる。

解説

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

データの個数が４倍になると「 log₂4n＋１」となり、log₂4n ＝log₂n＋２
であるから、２増えることになる。