二分探索

https://gyazo.com/c6a2b295ef419c2be961ef008bf4bac1

あなたは今、靴を買いたいと思って、靴の売り場に来たとする。

仮に、あなたの足のサイズが24.5だとして、どうやって探すだろうか。

例えば、売り場の中で、23と27の場所だけが分かっているとする。

table:靴のサイズ

23 27

とりあえず、真ん中の場所を見てみた。

table:靴のサイズ

23 25 27

真ん中に置いてあるサイズは25だった。ということは、今自分が探しているサイズは、25の場所よりも左側だということがわかる。

なので、23と25の間を探すことにした。

23と25の間の場所を見に行くと、

table:靴のサイズ

23 24 25 27

24があった。となると、今探しているサイズが 24.5なので、24よりも右側にあることがわかる。

なので、24と25の間を探すことにした。

table:靴のサイズ

23 24 24.5 25 27

あったあった。探していたサイズの24.5の場所がわかったぞ。

以上が二分探索を使って、目的の数値を探す方法である。

では、「11,24,36,42,58,63,77」の中から36を探すアルゴリズムを考えてみよう。

https://gyazo.com/a5194c825d83e190a584aadf22c08e1a

さっきの靴のサイズを探すときの考え方を、変数m,i,jを使って考えてみると、計算で割り出すことができることに気づくだろう。

さぁ、このように動くプログラムを作ってみよう。

kadai10

以下の作成例は未完成なので、このままでは動かない。

未完成の部分4箇所を考えて、二分探索のプログラムとして完成させよう。

code:kadai10

i = 0

j = 6

s = 36

count = 0

while i<=j:

count+=1

m = int(●●●●●●●●●●●●)

print("Hakken!",count)

break

●●●●●●●●●●●●●●

else:

●●●●●●●●●●●●●●