Q&A
logについている2は2乗ではなく、対数の「底」です。
基本情報技術者試験
2分探索法
・データ領域の中央値で比較し、探索範囲を絞りこみ、目的のデータを探し出す。
・データは、昇順もしくは降順に整列されてなければならない。
・データがN件のとき、「き」は何回目で見つかるか？
|1|2|3||4|5|6|7|8|
|:--|:--:|--:|
|あ|い|う|え|お|か|き|く|
【答え】３回目
公式ーーーーーーーーーーーーーーーーーーーーーー
平均比較回数：log2乗N回
最大比較回数：log2乗N＋1回
2x≦N<2x+1
ーーーーーーーーーーーーーーーーーーーーーーーー
上記の公式をどう使えば答えの3回目が見つかるかよくわからないため、
ご教授ください。
回答4件
0
公式で求めることができるのはあくまで「平均比較回数」と「最大比較回数」です。
この問題の場合はデータと値および検索する値も提示されているので公式で求めることはできません。
・データがN件のとき、「き」は何回目で見つかるか？
これ問題そのままでしょうか？回答が出ないです。
「データーが8件の以下の場合」ではないでしょうか？
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| あ | い | う | え | お | か | き | く |
以下のとおり３回です
0. 1～8の半分4の値えはきより小さい
0. 5(4+1)+8の半分6の値かはきより小さい
0. 7(6+1)+8の半分7の値きはきと同じ
もし問題文が
・データが8件のとき、「き」は平均何回目で見つかるか？
なら公式平均比較回数log2Nを使用してN=8なのでlog2 8=3と求まります。
投稿2017/03/03 05:45
編集2017/03/03 06:22
総合スコア7914
0
なぜかと言われれば、二分木探索とは、1回の探索で範囲を半分に絞り込むからです。
元のデータ個数が N として、探索回数が
1回： N/2
2回： N/4 (N/2 /2)
3回： N/8 (N/2 /2 /2）
…
n回： N/(2^n)
となりますから、最悪でも 2^n >= N となる n までの回数で探索が完了（対象個数が1以下になる）します。これを数学的に表現すると、log2N となります。
今回の場合、N=8 ですから、 log2 * 8 = 0.301 *8 = 2.408 なので、切り上げて 3 が答えです。
※平均試行回数でいうと切り上げずに 2.4 回がそのまま解になります
投稿2017/03/03 05:58
編集2017/03/03 06:03
総合スコア13703
log2Nの2は対数の底なのに、いつの間にか常用対数の真数になってる…
0
１〜８にデータがあり、N=8です。
探したい対象はきで、s="き"とします。
1
二分探索は、まず名前の通りデータを二分します。
範囲は1〜8なので
(1+8)/2 = 4 ※切り捨て
データから、4番目の"え"と"き"を比較すると、"き"のほうが大きいです。
つまり、sはデータの5〜8にあることがわかります。
2
更に範囲内の中央を取るために平均を取ります。
(8+5)/2 = 6
6番目の"か"と"き"を比較すると、"き"のほうが大きいです。
sはデータの7〜8にあることがわかります。
3
同様に
(7+8)/2 = 7
7番目の"き"と"き"を比較すると、等しいです。
sはデータの7番。探索終了です。
- なぜ、データがより上（または下）にあることがひとつのデータをみただけでわかるのか？
二分探索はデータが整列済みであることを前提としているからです。
- 公式は使わないのか？
例えば"き"を探すときは最大でも平均でもない比較回数(1回)になります。
回数が最大か平均かを判断できない場合は公式は無意味です。
投稿2017/03/03 05:46
総合スコア868
お返事遅くなり申し訳ありません。
ものすごくわかりやすい解説かと存じますが、私の理解が追い付いてないです。。。
以下質問です。
1
二分探索は、まず名前の通りデータを二分します。
範囲は1〜8なので
(1+8)/2 = 4 ※切り捨て
→データは８個しかないのになんで１＋８なんですか？
また、なんで切り捨てするのでしょうか？
データから、4番目の"え"と"き"を比較すると、"き"のほうが大きいです。
つまり、sはデータの5〜8にあることがわかります。
2
更に範囲内の中央を取るために平均を取ります。
(8+5)/2 = 6
２では更に範囲内の中央を取るために平均を取ります。と書いてあるのですが、
１の計算は平均を取ってるものではなかったのですか？
横から失礼。
1.要は、「真ん中」を知りたいのです。1〜8の真ん中は、並べてみると
12345678
の真ん中ですから、4と5の間になります。これを数値的に、(1+8)/2としています。
この答えは4.5と出ますが、配列の番号として使う以上、整数にする必要があります。切り上げでも切り捨てでもいいのですが、一般的にコンピュータでの整数の除算は余り切り捨てで出るため、切り捨てを採用しています。
2.これも、5〜8の「真ん中」を知りたいのです。説明は同じなので省略。
swordoneさん的確な回答ありがとうございます
>１の計算は平均を取ってるものではなかったのですか？
平均を取ってます。公式にするなら、
(範囲の下限+範囲の上限)/2
で平均が取れます。最初は1~8なので、これを代入して
(1+8)/2
としたわけです。
８/2でもいいですが、それをすると2回目以降で同じ公式が使えなくなるので避けました。
最近調べてて知ったのですが、この「足して2で割る」という方法は間違った方法(数値が大きいとオーバーフローを起こす)で、一時期多くの実装で間違っていたそうです。Javaでは1998~2006まで間違っていたとのこと(Wikipedia-二分探索より)。
正しい実装はこの例でいうと1+(8-1)/2とのこと。「最小値に区間の半分を足す」という方法ですね。
left+(right-left)/2
ってことですかね
文章題ではオーバーフローは起きえないので本題とはずれている気もしますが、勉強になります。
皆様理解が進みました。ありがとうございました。
0
回答としてはこちらのホームページをご覧ください
投稿2017/03/03 05:36
総合スコア93
あなたの回答
tips
プレビュー
