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

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

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

問14　　 ２分探索法での比較回数

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

ア　log₂ n 　　　　　イ　(log₂ n ＋1)／2

ウ　 n 　　　　　　　エ　 n ²

解説

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

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

　２分探索法での比較回数は、log₂ n である。

【平成11年春問30】