２分探索 バイナリーサーチ？

質問

初歩的な質問で恐縮ですが、どうぞよろしくお願いします。
２分探索　バイナリーサーチで、登録件数5000件のデータからある数値を探索する場合、平均探索回数をXとした場合
２（X：べき乗）＜＝5000＜２（13：べき乗）
となり、最大検索回数が13回、平均探索回数が12回となることなのですが？？？

これはどのように解法すればよいのでしょうか

回答No.2

ChateauAres

真面目に計算するまでもなく、２の１０乗が１０２４であることから、２の１１乗が２０４８、１２乗が４０９６・・・故に最大検索回数１３回は暗算ですぐ計算できますよ。

情報処理の世界では２の１６乗までは普通に暗記している人も多いです。

お礼

ChateauAresさま
そうですね。
私の場合、真面目というか頭の回転が鈍いのかもしれません。
そのように考えるというか、要領よく、ポイントを考え展開していけばいいのですね。
ありがとうがざいました。

回答No.1

ChateauAres

平均比較回数の公式は log2ｎ -1回なので、
log2 5000=Log 5000/Log 2=3.69897/0.30103=12.28

よって 12.28-1=11.28回になり、小数点以下を切り上げて１２回になります。

Log 5000の計算はウィンドウズの電卓を関数電卓モードにすれば、 5000 の後に log ボタンを押すと計算できますよ。

補足

ChateauAresさん

こんにちは
早速のご回答ありがとうございます。
とても嬉しいです。
それで、電卓で計算できるのはわかるのですが、
これが電卓使用不可、手計算しかも短時間で算出したいのですが・・・いかがなものでしょう