「お昼の放送」の思い出

プログラミングの問題で、二分探索をあまり理解していないのですが、どなたか教えて頂けないでしょうか?
よろしくお願いします。

Q1. 二分探索を行なっていて、配列のhead番目以上tail番目以下に探している数があることがわかっているとする。 head番目とtail番目の真ん中(i番目)が探している数より大きかった時、 探している数が存在する範囲として、最も適切なものを選びなさい。
1. head〜i-1
2. head〜i
3. i〜tail
4. i+1〜tail

Q2. 二分探索を行なっている時、求める値の存在する範囲が、配列のhead番目以上、tail番目以下の 範囲であるとする。headとtailの間隔を狭める様に、この2つの値を変えていくわけだが、 headとtailがどの様な関係になった時に、この配列に求める値が存在しないと言うことができるか? 最も適切なものを選びなさい。
1. head < tail
2. head == tail
3. head >= tail
4. head > tail

A 回答 (2件)

トランプを用意して手作業でやってみると分かりやすいと思います。



準備として1つのスート分を1~Kの順に並べます。

1.トランプの束を半分取る。
2.とった時に残った時のカードの数字が目的の数字より小さい場合は、残ったカードの束を3で使う。数字より小さい大きい場合は、手に取ったカードの束を3で使う。目的のカードが出たら終了。
3.目的の数字が出るまで1~2を繰り返す。

例えば目的のカードを8とした場合…
1-1回目.13枚の半分(切り捨て)の6枚を取る。
2-1回目.7が出たので残ったカードを使う。
1-2回目.残った7枚の半分の3枚を取る。
2-2回目.10が出たので手に取ったカードを使う。
1-3回目.手に取った3枚の半分1枚を取る。
2-3回目.目的のカード(8)が出たので終了。

という動きになります。

こうやって目的のカードを探した時に、カードが最初の並びで何番目だったかを返却しているのが二分探索です。

上の例では連続したカードですが、「カードが最初の並びで何番目だったかを返却する」事でデータが歯抜けの状態でも問題なくなります。
例えば、「1,3,4,6,11」の様な数字列でも見つけ出すことができます。

アルゴリズムは図や文章で開設される事が多いですが、そのまま理解する事はそれほど簡単ではありません。
自分でやってみると「こんな事が起こっているのか」と視覚的に分かるので是非手作業でやってみる事をお勧めします。
    • good
    • 0

配列にセットされている値はheadからtailに向かってだんだん大きくなるように並んでいますか?


それともその逆ですか?
問題文をそういったことを考慮しながらよく読んで、二分検索法で求める値を探していく際の様を頭の中に浮かべながら考えるとよいです。
で、プログラム言語で考えない方がよいです。あくまで日常使っている言語と数が並んだ図で考えましょう。あとはチャート図ですか。

以下参考に。

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86 …

ちなみにGoogleなどで「二分検索」とか「バイナリーサーチ」といったキーワードで検索すると様々な解説ページがヒットするかと思います。
そういう物の中からご自身にあった(=分かりやすいと思える)ものを選ばれるとよいです。

参考まで。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


おすすめ情報