No.1ベストアンサー
- 回答日時:
「二分探索」のことですね。
では,お答えします。二分探索のポイントは,文字どおり,「半分半分にする」ことです。具体的な数で考えてみます。アルゴリズムの概略を追うので,細かい点はあまり考えませんが,これは気にしなくても大丈夫です。
【16 個から探す場合】
16 個の半分→8 個
8 個の半分→4 個
4 個の半分→2 個
2 個の半分→1 個
で,4 回です。
【65,536 個から探す場合】
65,536→32,768→16,384→8,192→4,096→2,048→1,024→512→256→128→64→32→16→8→4→2→1
で,16 回です。
さて逆に,「m 回の比較で何個から絞り込めるか」を考えます。1 回探索回数が増えると,2 倍の探索対象から絞り込むことができるのはよろしいでしょうか。
たとえば,4,096 個から絞り込める探索回数より 1 回多いと,8,192 個から絞り込めるということです(上の例をもう一度ご覧ください)。
具体的には,
- 1 回の探索で 2 個から絞り込めます
- 2 回の探索で 4 個から絞り込めます
- 3 回の探索で 8 個から絞り込めます
- 4 回の探索で 16 個から絞り込めます
- 5 回の探索で 32 個から絞り込めます
- 6 回の探索で 64 個から絞り込めます
- 7 回の探索で 128 個から絞り込めます
- 8 回の探索で 256 個から絞り込めます
ということがおわかりでしょうか。これを式で表すと,m 回の探索回数で,2^m(2 の m 乗)個から絞り込めるということです。つまり,2^m 個からの探索回数は m 回です。
ここで,対数を登場させます。対数は,「真数は底の何乗か」を表すものですから,
- 8 の,底を 2 とした対数は 3(2^3 = 8)
はよろしいでしょうか。では,「2^m の,2 を底とした対数」はいくらかというと,「2^m(真数)は 2(底)の m 乗」なので,「m」になります。これは,対数の底を 2 として,
log 2^m = m
と書けるでしょう。
ですから,探索対象が 2^m 個のとき,比較回数は log 2^m,すなわち m 回になります。
では n 個から探索する場合はというと,同様に
log n [回]
になるはずです。
二分探索では,「1 回増えるたびに 2 倍の探索範囲から探せる」,すなわち,2^m の m が 1 増えます。この,m(指数)を取り出す操作が log をとることなので,探索回数に log が出てきます。
二分探索は,探索対象が倍になっても,回数は 1 回しか増えません。これは,すぐれた方法です。線形探索では,探索対象が倍になると,回数も倍になるでしょう。
以上,おわかりいただけたでしょうか。
No.2
- 回答日時:
2分探索法ですね。
簡単のため、32個の中を探索する例を考えます。半分づつにしていけば、32,16,8,4,2の中でどちらの半分にあるかですから、5回の探索です。
これが128個の中からだと、128,64,32,16,8,4,2と、7回の探索になります。
つまり、全個数をNとすれば探索回数はlog2(N)です。平均とあるのは、Nが丁度2のべき乗にはなっていないとき、運不運があるので、それを平均として考えるという意味でしょう。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
このQ&Aを見た人はこんなQ&Aも見ています
-
歩いた自慢大会
「めちゃくちゃ歩いたエピソード」を教えてください。 長時間でも長距離でも結構です。
-
フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
あなたが普段思っている「これまだ誰も言ってなかったけど共感されるだろうな」というあるあるを教えてください
-
映画のエンドロール観る派?観ない派?
映画が終わった後、すぐに席を立って帰る方もちらほら見かけます。皆さんはエンドロールの最後まで観ていきますか?
-
海外旅行から帰ってきたら、まず何を食べる?
帰国して1番食べたくなるもの、食べたくなるだろうなと思うもの、皆さんはありますか?
-
天使と悪魔選手権
悪魔がこんなささやきをしていたら、天使のあなたはなんと言って止めますか?
-
二分探索の平均探索回数
その他(プログラミング・Web制作)
-
2分探索法の平均比較回数
情報処理技術者・Microsoft認定資格
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
y=x^x^xを微分すると何になりま...
-
∫{x/(x+1)}dxの解き方
-
自然対数をとる?とは・・・
-
∫log(x^2)dxの不定積分を教えて...
-
log3^1はなんで0になるんですか?
-
関数電卓の使い方
-
対数・指数の値の大小
-
log2の5は?
-
1/(1-x)や1/(1+x)の積分形
-
lim[x→0]x/1log{log(x+e)} が解...
-
[(e^x)/(e^x+e^-x)]の積分
-
e^x=2のときのxの求め方
-
256は2の何乗かを求める式
-
(logx-1)^2の微分を教えて欲し...
-
∫log sinx dxや∫log cosx dx ...
-
両対数グラフでの直線の傾きと...
-
eの指数の計算がわかりません。
-
lim[x→∞]log(1+x)/x これってど...
-
5の30乗は何桁の数か。ただし、...
-
超初歩的質問ですが・・
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
y=x^x^xを微分すると何になりま...
-
1/(1-x)や1/(1+x)の積分形
-
∫{x/(x+1)}dxの解き方
-
e^x=2のときのxの求め方
-
自然対数をとる?とは・・・
-
lim[x→∞]log(1+x)/x これってど...
-
256は2の何乗かを求める式
-
透過率から吸光度を計算する際...
-
なぜxがe^logxと変形できるので...
-
lnをlogに変換するには・・
-
log3^1はなんで0になるんですか?
-
超初歩的質問ですが・・
-
eの指数の計算がわかりません。
-
∫log(x^2)dxの不定積分を教えて...
-
log2の5は?
-
y=x^(1/x) の 微分
-
関数電卓の使い方
-
2を何乗すると6になりますか? ...
-
教えてください、分かりません
-
∫1/x√(x^2+1) の積分について。
おすすめ情報