応用情報技術者 試験情報＆徹底解説

かなり初歩的な質問です。
完全2分木における探索で要素を半分にしながら比較することは理解できました。しかし、比較回数のlog2nの要素数nの数え方がわかりません。
例えば完全2分木の深さが2であったとします。この時、要素数が7だと思っていますが、最大比較回数が3であるため計算とlog2nと一致しません。なぜ要素数が8になるのかご教授ください。

繰り上げてください。
log2底の7は2.8とかそこらへんになると思います。ただし演算回数は離散的であり少数にはなりません。平均ではなく最大であることにご注意を。基本的には繰り上げて3となります。nが8なわけではないのです。実際深さ2の完全二分木を適当にたどれば葉にたどり着くとき節を3回参照してると思います。