基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

解説がよく分からないんですが、
2000→1000→500→250→125→63→32→16→8→4→2→1で11回比較
最後に1を足して12回比較ではないんですね。

問題文に「"該当するキーが必ず表中にあることが分かっているとき"」とあるのですが、
この一文で最後の1回が省略出来たということではないんですか？

最後の1個に絞れた時の値確認って、"比較"には含まれないんですかね...。
なんというか、日本語で躓いている感...。

2000→1000→500→250→125→63→32→16→8→4→2→1で11回比較
ですが、最後の1回は11回目で、12回目はありません。

もう少し具体的に書いてみます。仮に、外部から入力したキー(探索したいキー)が、先頭(1個目)にあるとします。

①1000個目と比較
②500個目と比較
・
・
⑨4個目と比較
⑩2個目と比較
⑪1個目と比較

横から失礼します。
例えば配列が八個あったとして先頭にデータがあるとすると。
まず  (1+8)/2 で  4を比較。    その次に(1+3)/2で  2を比較    その次に(1+1)/2で1を比較

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

今回の例も  log2 2000 = 約10なので    答えはイです。  

ろっぺんさん

正解はウですよ。管理人様の解答でも、IPAの解答でもウです。

ろっぺんさんの八つの配列の例では、最大比較回数は4回です。先頭にデータがある場合は3回ですが、最後尾にデータがある場合は4回です。

まず  (1+8)/2 で  4を比較    その次に(5+8)/2で  6を比較    その次に(7+8)/2で7を比較    その次に(8+8)/2で8を比較

全部で4回です。4＝[log2 8]＋1です。

なお、この問題の解説で、
最大比較回数は[log2 N＋1] 回
となっているのは、
最大比較回数は[log2 N]＋1 回
の誤りですので、別スレで修正依頼します。

横から失礼します。

最大比較回数は[log2 N]＋1 回
と書くと感覚的に非常にわかりにくいので、
最大比較回数＞[log2 N]を満たす最小の整数
と書くほうが理解しやすいかと思います。

皆様、ご丁寧に解説ありがとうございました。理解出来ました。

数学が弱く、[log2 N]＋1の意味すら怪しかったのですが、要するに

33～64、65～128、129～256（例）の最大比較回数が同じという解釈で大丈夫ですよね？

33～64、65～128、129～256
ではなく
32～63、64～127、128～255
です。

[log2 N]＋1は、それぞれ6、7、8です。

ご指摘があったので（あれ～～っ）と思い、4と7の最大比較回数を考えました。

どちらも最大で3回比較するんですね・・・

3→2を比較→1を比較  最大2回
4→3を比較→2を比較→1を比較  最大3回
7→4を比較→2を比較→1を比較  最大3回
8→5を比較→3を比較→2を比較→1を比較  最大4回

図で言うと、  ○○○／○○○→○○／○・・・→○／○・・・・  こういう、配列を分割する考え方をしていたのがややこしかったようです。

○○①○○○→×××○②○→×××③××  こんな感じで、真ん中に近い配列を1個ずつ調べる  という捉え方をしたらすんなり頭に入ってきました。

解説・ご指摘ありがとうございました！

(No.8)の内容がちょっと気になったので、念のためです。
ただし、中央値を何番目とするかは、(左端＋右端)／2(小数以下切捨て)の前提です。

4個の場合
  先頭にデータがある場合・・・2を比較→1を比較  2回
  最後尾にデータがある場合・・・2を比較→3を比較→4を比較  3回

8個の場合
  先頭にデータがある場合・・・4を比較→2を比較→1を比較  3回
  最後尾にデータがある場合・・・4を比較→6を比較→7を比較→8を比較  4回