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

平成18年 秋期 基本情報技術者 午前 問14
問14   2分探索法での比較回数

 昇順に整列された n 個のデータが配列に格納されている。 探索したい値を2分探索法で探索するときの,およその比較回数を求める式はどれか。

ア log2 n       イ (log2 n +1)/2

ウ  n         エ  n 2


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

解説

 2分探索法は、整列されたデータの中央の値と対象データを比較し、 それより前方にあるか後方にあるかを判断する。 前方にデータがある場合は、前半分のデータの中央のデータと比較し、 後方にデータがある場合は、後半分のデータの中央のデータと比較する。

 この操作を繰り返すことによって、検索する方法である。

 2分探索法での比較回数は、log2 n である。

【平成11年春 問30】


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