２分探索法 『成功・不成功探索一回の実行時間を求める』

質問

Ｃ言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。

----------課題----------
整列されているＮ個のデータに対して、その中にｖがあるかどうかを判断する２分探索プログラムを実行する
Ｎの値を10^6、5×10^6、10^7、5×10^7、10^8
と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。
このとき、Ｎと実行時間の関係はどのようになっているか（１００字程度で）
　　Ｎ　　成功探索　　不成功探索
　10^6　　＊＊＊秒　　　＊＊＊秒
5×10^6 　＊＊＊秒　　　＊＊＊秒
　10^7　　＊＊＊秒　　　＊＊＊秒
5×10^7 　＊＊＊秒　　　＊＊＊秒
　10^8　　＊＊＊秒　　　＊＊＊秒
----------------------------------------

～↑を元に作成したプログラム（成功探索の場合）～
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T 1000000
#define N 100000000

int a[N];
int main(void)
{
clock_t t1,t2; int t;
int i;
int l, r, k, v, m;
for (i = 0; i < N; i++) a[i] = i;
t1=clock();
for (t = 0; t < T; t++) {
v = rand() % N;

l=0; r=N-1; k=-1;
while (r >= l) {
m = (l+r)/2;
if (v == a[m]) { k=m; break; }
if (v < a[m]) r = m-1; else l = m+1;
}

}
t2=clock();
printf("cpu time=%10.6f[micro sec]\n",(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T));

return 0;
}

↑a[i]すべてに０～Ｎ－１を代入し、ｖにランダムに０～Ｎ－１の値を代入する。２分探索法で、ｖ＝a[i]となったら終了する。
実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位：マイクロ秒

として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。

↑のプログラムをそれぞれのＮで実行したところ
Ｎ＝
　10^6で実行・・・1.016 0.891 0.969 1.155 1.14 [micro sec]
5×10^6で実行・・・1.422 1.500 1.563 1.250 1.406 1.297
　10^7で実行・・・1.750 1.360 1.37 1.407 1.672 1.531
5×10^7で実行・・・1.859 1.797 1.812 1.800
　10^8で実行・・・2.062 2.140 2.320 2.500

このような結果になりました。
これで正しいのでしょうか？もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか？
でも、Ｎが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。

次に
不成功探索では↑のプログラムの
乱数ｖのところを変化させて
v=rand() % N；という箇所を
ｖ＝Ｎ;としました。
a[i]には０～Ｎ－１が入っているので、ｖ＝Ｎとすれば必ず不成功になるはずですよね？
こうして実行してみると
Ｎ＝
10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても
0.719 0.54 0.625 0.534 [micro sec]
に近い値ばかり出てしまい、正しい値とは到底思えません。

不成功探索は成功探索より時間がかかるはずですよね？なのになぜこのようになってしまったのでしょうか？

後、Ｎと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか？
こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。

長々とスイマセン。
少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。

回答No.1

gau_puzzler · ベストアンサー

ざっとプログラム見ましたが、特に問題は無いように見受けられます
そもそも探索ですから（Ｎ＝１６として）
１回目で見つかる場合もあるし、最悪４回目で見つかる、みつからないとなりますよね？（２分探索なので）
ですので平均を計算する必要があります
するとだいたい、o LOG nで検索できるとなります

ちなみに不成功探索ですがv=Nだと１回目の探索ですぐ「ないぞ」とわかってしまうのでだめです
a[i] = i*2;
とでもしておいて（データはすべて偶数）
v = N/2;
ならいいんじゃないですか？

お礼

早速の返答ありがとうございます。とても参考になりました。

確かに、何回も繰り返して、１回目で終了することが多ければ時間は短くなり、逆に最大回数で終了するのが多ければ時間は多くかかってしまいますね。
あれほど差がでるものなのかな？と思っていましたが、納得しました。

不成功探索ですが、色々試してやって見たのですがやはり上手く行きません。
データを偶数にしてｖに奇数を入れてやってみましたが同じような値が出てしまいます。

質問なんですが、ｖ＝Ｎの場合なぜ一回目の探索で「ない」と分かってしまうのでしょうか？
常に「r > a[i]」なので、ｌ＝ｍ＋１をしていってｒ＞ｌの時終了するので最大回数まで行くと思ったのですが・・・

回答No.3

gau_puzzler

確認しますが、実行環境はなんですか？
linux?、windows?
さらに開発環境はどうですか？
gcc?、visualC?

お礼

色々、ありがとうございます
一応、問題は解決しました…
中途半端な形になって申し訳ないのですがここで締め切らせて頂きます。スイマセン。

回答No.2

gau_puzzler

>質問なんですが、ｖ＝Ｎの場合なぜ一回目の探索で「ない」と分かってしまうのでしょうか？
>常に「r > a[i]」なので、ｌ＝ｍ＋１をしていってｒ＞ｌの時終了するので最大回数まで行くと思ったのですが・・・
あ！、そうですね勘違いしてました
たしかに最大回数いきます
（ついでにV=N/2+1でした）

それでなんですが、10^8だと探索回数は２７回なので
たかだた２７のループの実行速度はあっというまに終わってしまうので
誤差の範囲内なのでだめでしょう

ちゃんと計測するのなら以下のように
時間測定開始
１００００回ループ
　検索する部分
時間測定終了
とやって、測定値を１００００で割ったらどうでしょうか？

お礼

時間測定開始
1000000回ループ
　検索する部分
時間測定終了

(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T)

↑として、一応やっています…（先生から同じようなことを言われてループして、そのループした回数を割って平均を出しました）

友達に聞いたら、不成功探索時間は成功探索より短くて良いと言われたんですが・・・
なぜ短くなってしまうのかが分かりません。