基本情報技術者 平成20年秋期 午前問13 についてです。

Question

比較回数は11回とのことですが、よくわかりませんでした。

例えば配列が8つだとします。先頭の1にデータがあったとして・・・。

まず (1+8)/2 で 4を比較。 その次に(1+3)/2で 2を比較 その次に(1+1)/2で1を比較

全部で三つです。 これは log2 8 と同じ値なので

今回の例も log2 2000 = 約10なので 答えはイだと思われます。

だれかご解説お願い致します。

Comments

[x_x]

みんなが受けたわけではありません。何が何やらさっぱりです。

Answer 1

最大探索回数の考え方です。

1~8の場合

①4以上か
YES→48
②6以上か
YES→6～8
③7以上か
YES→78
④7か（最終比較）

となり4回です。

Answer 2

質問者の計算で求まるのは「平均比較回数」です。
今回は比較回数の最大を問われていますので、最大比較回数を求める必要があります。

探索要素数をNとすると、2分探索法の平均比較回数は log2N 回、最大比較回数はlog2N＋1 回です。

Answer 3

平均比較回数と最大比較回数の違いです。