algorithm - 二分探索性能分析

Question

二分探索アルゴリズムの比較木の葉がすべて同じレベルまたは隣接するレベルにあるとすると、n 個の項目のリストを検索する際に行われるキーの比較はlog(n)、最悪の場合、+1 の天井になると言えますか?log(n) + 1平均的なケースでは？

だいたいlog(n) + 1最悪でlog(n)平均であると本に書いてありましたが、最悪の場合は n を与えれば決まっていると思いますので、おおよその値を出す必要はなく、平均はプラス 1 でいいと思います。

コードは次のとおりです。

Error_code recursive_binary_1(const Ordered_list &the_list, const Key &target, int bottom, int top, int &position)
{
 Record data;
 if(bottom < top) {
   int mid = (bottom + top)/2;
   the_list.retrieve(mid, data);
   if(data < target)
     return recursive_binary_1(the_list, target, mid + 1, top, position);
   else
     return recursive_binary_1(the_list, target, bottom, mid, position);
  }
  else if(top < bottom)
    return not_present;
  else {
    position = bottom;
    the_list.retrieve(bottom, data);
    if(data == target) return success;
    else return not_present;
  }
}

そうでない場合は修正してください。