アルゴリズム:2分探索の時間計算量

アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。

/*
２分探索
*/
#include <stdio.h>
/*--- 要素数nの配列aからkeyと一致する要素を２分探索 ---*/
int bin_search(const int a[], int n, int key)
{
int pl = 0;/* 探索範囲先頭の添字【1】 */
int pr = n-1;/* 〃 　末尾の添字 【2】*/
int pc; /* 　 〃 　中央の添字 */

do {
pc = (pl + pr) / 2;/*【3】*/
if (a[pc] == key)/* 探索成功【4】 */
return (pc);/*【5】*/
else if (a[pc] < key)/*【6】*/
pl = pc + 1;/*【7】*/
else /*【8】*/
pr = pc - 1;/*【9】*/
}
while (pl <= pr);/*【10】*/

return (-1);/* 探索失敗【11】 */
}


のプログラムがありますが、【1】から【11】までの
実行回数と計算量は次のようになるそうですが、
　　　実行回数　　　計算量　
【1】　　1　　　　　　　O(1)
【2】　　1　　　　　　　O(1)
【3】　　logn　　　　　O(logn)
【4】　　logn　　　　　O(logn)
【5】　　1　　　　　　　O(1)
【6】　　logn　　　　　O(logn)
【7】　　logn　　　　　O(logn)
【8】　　logn　　　　　O(logn)
【9】　　logn　　　　　O(logn)
【10】　　logn　　　　　O(logn)
【11】　　1　　　　　　　O(1)

なぜ【3】や【4】がlognになるんでしょうか？
詳しく教えてください。
よろしくお願いします。

No.5 回答者： ymmasayan 回答日時： 2005/05/28 22:38

No.2、No.4です。

No.2の補足質問にお答えします。
No.4を見ていただくと大体分かると思いますが。

>>　平均ループ回数はデータが半分見つかる3.27回です。
>　というところですが、なぜ3.27というのがでてくるのですか？
１回×１個＋２回×２個＋３回×４個＋４回×８個＝４９回
平均は１５で割ると４９／１５＝３．２７回です。

>>　log(2)15≒3.91と比べると差は0.64
>　で差ってどうして出すのですか？
3.91-3.27=0.64のことですね。ちょっと紛らわしかったですね。
差が１に近いということを示したかっただけです。
No.4ではきちんと書いておきました。

>　理論値は(logｎ)－１というのは、常識で知っている物ですか？
はい。２分探索を完全にマスターしたと言うには、知っているべきでしょうね。
ちなみに基本情報技術者試験では出題範囲に入っています。

No.4 回答者： ymmasayan 回答日時： 2005/05/28 22:06

No.2です。

>　データ数ｎに対してlogn回になるというところで
>　logn自体になるのはどうしてですか？
>　ちなみに10の場合はどう説明できますか？

あまり小さいｎで議論すると誤差が大きくなります。
１０２３で考えて見ましょう。
１回ループするごとに探索範囲が半分になっていきます。
探索が全て完了するために必要な回数をmとすると、
2^m≧1023が成立すればいいことになります。
両辺の２の対数をとるとm≧log1023ということになります。
一般化すると最大探索(ループ)回数≧logｎとなります。
平均探索(ループ)回数は最大探索(ループ)回数－１です。
半分探し終わったところが平均ですから最大－１ということです。

実際にn=1023で半分半分で計算してみると最大10回、平均9.01回になります。
理論値はlog1024＝10を使って最大約10回、平均約9回でほとんど一致します。

No.3 回答者： sunasearch 回答日時： 2005/05/28 21:49

＃１です。

処理の回数が、２倍、４倍、８倍と倍々になっていくときは、「２のn乗」と指数を使うと思います。

今回の二分探索は、半分ずつデータの数ｎを絞り込んでいくわけですから、指数関数の逆関数の対数になるというわけです。

No.2 回答者： ymmasayan 回答日時： 2005/05/28 20:43

簡単な例で説明します。

１５個のデータがあるとします。
２分割づつしていきますから、確率で考えると
１回目で見つかるのは１個
２回目で見つかるのは２個
３回目で見つかるのは４個
４回目で見つかるのは８個
ですね。これで全部見つかります。
最大ループ回数は４回ですが、
平均ループ回数はデータが半分見つかる3.27回です。
これはlog(2)15≒3.91と比べると差は0.64になります。
データ数を増やした時の平均ループ回数の理論値は(logｎ)－１ですが、
これをＯ記法で表すと(－１)が無視されてＯ(logｎ)となります。

ちなみに、最大ループ回数の理論値はlogｎで当然これもＯ記法でＯ(logｎ)です。

言うまでもないことですが上記ではlogの底の２を省略しています。

この回答への補足

ありがとうございます。
＞平均ループ回数はデータが半分見つかる3.27回です。
というところですが、なぜ3.27というのがでてくるのですか？
log(2)15≒3.91と比べると差は0.64
で差ってどうして出すのですか？
理論値は(logｎ)－１というのは、常識で知っている物ですか？

質問が多くてすみません。初心者なのでよろしくお願いします。

補足日時：2005/05/28 21:28

No.1 ベストアンサー 回答者： sunasearch 回答日時： 2005/05/28 19:55

3,4,6,7,8,9はすべて、

ループの中で実行され、ループの回数が、
データ数ｎに対してlogn回になるからです。

この回答への補足

ありがとうございます。
データ数ｎに対してlogn回になるというところで
logn自体になるのはどうしてですか？
ちなみに10の場合はどう説明できますか？

補足日時：2005/05/28 20:40