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

基本情報技術者の過去問について
平成20年秋期試験午前問題 問13
https://www.fe-siken.com/s/kakomon/20_aki/q13.html

①
>2^10＝1024、2^11＝2048なので、[log2 2000]は10になります。
とあるのですが、なぜそうなるのかがさっぱりわかりません
そもそもlogとはなんでしょうか？
平均比較回数、最大比較回数の違いも教えていただけると助かります

②
log2 8=3 の場合平均比較回数が3なのは8=2^3でわかるのですが、最大比較回数は+1で4ということですよね？
8→4→2→1 ではどう頑張っても3回しか2分できないと思うのですがなぜ4なのでしょうか？

①
>そもそもlogとはなんでしょうか？
logは対数です。
log2 8 = 3
「2を何乗したら8になりますか？」「3です」といった事を表しています。

また[log2 2000]の[]部分はガウス記号です。
[x]と書いた場合、 ｎ ≦ x ＜ n＋1 を満たすただひとつの整数を表します(nは整数)。
例えば[2.5]であれば 2 ≦ 2.5 ＜ 3 なので[2.5]=2となります。

>>2^10＝1024、2^11＝2048なので、[log2 2000]は10になります。
log2 2000を計算すると10.96578...になりますが計算する必要はありません。
ガウス記号があるからです。
対数で書くとこうなります。
log2 1024 = 10
log2 2048 = 11
つまり2を何乗したら2000になるか、という数は10～11の間にあることがわかります。
log2 2000 = 10～11の間
だから[log2 2000]=10となるわけです。

あ、解説文にも一応書いてありました。
>2分探索法の平均比較回数は [log2N] 回、最大比較回数は[log2N]＋1 回です(※[a]はaを超えない最大の整数を表しています)。

>平均比較回数、最大比較回数
・平均比較回数
目的のデータが一発で見つかる事もあれば、最後の最後で見つかることもありますよね。
じゃあ平均的には何回くらいで見つかるの？というのが平均比較回数です。

・最大比較回数
探索の一番最後で見つかった時の比較した回数です。
以下の②で説明しているのも最大となる例です。

②
2分する回数ではなく、比較する回数です。
プログラムで考えるとわかりやすいかもしれません。
2分探索は目的データと中央値を比較して、一致しなければ2分する事を繰り返します。

N=8でNは1,2,3,4,5,6,7,8だったとして、目的とするデータが8だとしましょう。
（中央値はNが割り切れない時は小さい側とします。N=9の中央値は5でN=8の中央値は4です）
探索1回目→8個のうち中央値4と比較、一致せず→5,6,7,8に絞る。
探索2回目→4個のうち中央値6と比較、一致せず→7,8に絞る。
探索3回目→2個のうち中央値7と比較、一致せず→8に絞る。
探索4回目→1個のうち中央値8と比較、一致。
終了。

2分したのは3回ですが比較したのは4回ですね。

これで合ってるか自信はないのですが…私はこう理解してました。
間違ってたらごめんなさいｗ

とてもわかりやすい解説ありがとうございます！！

ガウス記号を知らなかったことと、最大比較回数を2分する回数と勘違いしていたので理解できず困っていました(汗)
また分からなかったら質問しますので今回のように教えていただけると非常に助かりますm(__)m