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

平成21年 春期 基本情報技術者 午前 問07
問07   2分探索法の比較回数

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

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

ウ  n             エ  n 2


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

解説

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

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

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

【平成18年秋 問14】

【平成11年春 問30】


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