基本情報処理技術者試験問題の解答への質問です。

質問

基本情報処理技術者試験問題の解答への質問です。

現在、基本情報処理技術者試験問題を勉強しています。

平成20年秋期午前問13の問題の答えですが、ネット上で見る解答では11回ですが、私が解くと10回になってしまいます。

キー値の個数　　　比較回数
　1個　　　　　　　 0回
2～3個　　　　　　　1回
4～7個　　　　　　　2回
8～15個　　　　　　 3回
16～31個　　　　　　4回
・・・・
1024～2048個 　　　10回
どこがおかしいのか、どなたか教えてください。

なお、問題は　以下の通りです。
　2,000 個の相異なる要素が，キーの昇順に整列された表がある。外部から入力したキーによってこの表を２分探索して，該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。

ア　9　　　　　　 イ　10　　　　　　 ウ　11　　　　　　 エ　12

回答No.2

mtaka2 · ベストアンサー

aとbの比較について、通常「a<b(もしくはa>b)が成り立つかそうでないか」で比較一回になります。

一回の比較で「a<b」「a=b」「a>b」の三択が一つに絞り込めることにはなりません。
この三択から絞り込むには比較が2回必要になります。
(「a<b」かどうかと「a=b」かどうかを調べ、両方成り立たなければ「a>b」と判定、など)

補足

質問者です。

なるほど。
> 通常「a<b(もしくはa>b)が成り立つかそうでないか」で比較一回になります。
ということは、３個のデータについては、表の真ん中の値で比較すると、
試験値より大きければ最初の１つに、そうでなければ、真ん中と最後の値に絞り込まれる
わけですね。
２分探索とは、２グループに分けてどちらに入るかで探索するやり方なのだと、今ようやく
理解しました。ありがとうございました。

回答No.1

ok-kaneto

キー値の個数　　　比較回数
　1個　　　　　　　 0回
2個　　　　　　　1回
3～4個　　　　　　　2回
5～8個　　　　　　 3回
9個～16個　　　　　　4回
・・・・
1024～2048個 　　　11回

ですね。
http://computer.trident.ac.jp/license/examin/j20-am_autumn.html

お礼

私が間違っていました。おっしゃっている内容がようやく理解できました。ありがとうございました。

補足

質問者より

キー値の個数が３個の場合、真ん中を検査することにより、比較回数は１回で済むと思っています。
理由は、『該当するキーが必ず表中にあることが分かっている』からです。どうでしょうか？