基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成17年 春期 基本情報技術者 午前 問15
問15   2分探索の最大探索回数

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

ア 1回増える。      イ 2回増える。

ウ 約2倍になる。      エ 約4倍になる。


解答←クリックすると正解が表示されます

解説

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

データの個数が4倍になると 「 log24n+1 」 となり、log24n =log2n+2
であるから、2増えることになる。


[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]