近似のようなことについて

質問

0 < p < a
であり、a の値は分かっているが p の値は不明であるとします。
ある値 x について質問すると
「 x < p 」もしくは「 x > p 」 という答えが得られるとすれば、
できるだけ少ない質問回数で、できるだけ p に近い値を知るには
質問に用いる値をどのような規則に従って決めればいいでしょうか。

回答No.2

okormazd · ベストアンサー

2分探索(バイナリ―サーチ)

xが質問の値で、pを求めるとする。

1.
x1=(0+a)/2=a/2とする。

2.
(1)
p>x1 なら、
x2=(x1+a)/2=(a/2+a)/2=3a/4とする。
(2)
p<x1なら、
x2=(0+x1)/2=a/4とする。

3.
(1)
2.(1)の場合、
p>x2なら、
x3=(x2+a)/2=(3a/4+a)/2=7a/8とする。
(2)
p<x2なら、
x3=(x1+x2)/2=(a/2+3a/4)/2=5a/8とする。
(3)
2.(2)の場合、
p>x2なら、
x3=(x2+p1)/2=(a/4+a/2)/2=3a/8とする。
p<x2なら、
x3=(0+x2)=(a/4)/2=a/8とする。

4.
以下同様にしてx=pに(近く)なるまでくりかえせばいい。

1回調べるごとに探す範囲が半分になっていく。
始め、a/2でどっち側にあるか調べる。これで次に調べる範囲が半分になる。
次に、xとpの大小関係に応じて、a/4、3a/4のうちどれかと比べる。
前に比べたa/2より小さいということなら、a/4と比べればいいし、a/2より大きいということなら、3a/4と比べる。
これで次に探す範囲が、1/4になる。

さらに、前のxとpの大小関係に応じて、a/8、3a/8、5a/8、7a/8のどれかとくらべる。
a/4より大きいというなら、x=(a/4+a/2)/2=3a/8と比べるし、3a/4より小さいなら、x=(a/2+3a/4)/2=5a/8と比べる。
これで次に探す範囲が、1/8になる。

つぎは、a/16、3a/16、5a/16、7a/16、9a/16、11a/16、13a/16、15a/16のどれかと比べるのだが、どれと比べるかは、前の大小関係による。

要するに探す範囲が半分になるようにxが決められていく。

2分探索(バイナリ―サーチ)で検索しましょう。

お礼

詳しい説明をありがとうございました。
大変たすかりました。

回答No.1

suzukikun

間隔の半分を基準にしていくのがよいのでは？

お礼

ありがとうございます。
確かに最初の質問は x = a / 2 にするのがいいようですね。