プログラミングの問題で、二分探索をあまり理解していないのですが、どなたか教えて頂けないでしょうか?
よろしくお願いします。
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件)
- 最新から表示
- 回答順に表示
No.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」の様な数字列でも見つけ出すことができます。
アルゴリズムは図や文章で開設される事が多いですが、そのまま理解する事はそれほど簡単ではありません。
自分でやってみると「こんな事が起こっているのか」と視覚的に分かるので是非手作業でやってみる事をお勧めします。
No.1
- 回答日時:
配列にセットされている値はheadからtailに向かってだんだん大きくなるように並んでいますか?
それともその逆ですか?
問題文をそういったことを考慮しながらよく読んで、二分検索法で求める値を探していく際の様を頭の中に浮かべながら考えるとよいです。
で、プログラム言語で考えない方がよいです。あくまで日常使っている言語と数が並んだ図で考えましょう。あとはチャート図ですか。
以下参考に。
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86 …
ちなみにGoogleなどで「二分検索」とか「バイナリーサーチ」といったキーワードで検索すると様々な解説ページがヒットするかと思います。
そういう物の中からご自身にあった(=分かりやすいと思える)ものを選ばれるとよいです。
参考まで。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【大喜利】【投稿~11/12】 急に朝起こしてきた母親に言われた一言とは?
- ・好きな和訳タイトルを教えてください
- ・うちのカレーにはこれが入ってる!って食材ありますか?
- ・好きな「お肉」は?
- ・あなたは何にトキメキますか?
- ・おすすめのモーニング・朝食メニューを教えて!
- ・「覚え間違い」を教えてください!
- ・とっておきの手土産を教えて
- ・「平成」を感じるもの
- ・秘密基地、どこに作った?
- ・【お題】NEW演歌
- ・カンパ〜イ!←最初の1杯目、なに頼む?
- ・一回も披露したことのない豆知識
- ・これ何て呼びますか
- ・チョコミントアイス
- ・初めて自分の家と他人の家が違う、と意識した時
- ・「これはヤバかったな」という遅刻エピソード
- ・これ何て呼びますか Part2
- ・許せない心理テスト
- ・この人頭いいなと思ったエピソード
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・あなたの習慣について教えてください!!
- ・ハマっている「お菓子」を教えて!
- ・高校三年生の合唱祭で何を歌いましたか?
- ・【大喜利】【投稿~11/1】 存在しそうで存在しないモノマネ芸人の名前を教えてください
- ・好きなおでんの具材ドラフト会議しましょう
- ・餃子を食べるとき、何をつけますか?
- ・あなたの「必」の書き順を教えてください
- ・ギリギリ行けるお一人様のライン
- ・10代と話して驚いたこと
- ・家の中でのこだわりスペースはどこですか?
- ・つい集めてしまうものはなんですか?
- ・自分のセンスや笑いの好みに影響を受けた作品を教えて
- ・【お題】引っかけ問題(締め切り10月27日(日)23時)
- ・大人になっても苦手な食べ物、ありますか?
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・ちょっと先の未来クイズ第4問
- ・【大喜利】【投稿~10/21(月)】買ったばかりの自転車を分解してひと言
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・あなたの習慣について教えてください!!
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
配列数式の解除
-
特定のセル範囲で4文字以上入力...
-
VB6 配列を初期化したい
-
配列変数の添字が範囲外ですと...
-
for each の現在の配列ポインタ...
-
エクセルで最小値から0を除く方法
-
2つ以上の変数を比較して最大数...
-
えfor文とか使っちゃう時点で時...
-
AES暗号にて、AES_set_encrypt_...
-
配列の内容に重複をなくすには...
-
subの配列引数をoptionalで使う...
-
VBA 1次元配列を2次元に追加する
-
配列を任意の数値で埋める方法
-
エクセルマクロで配列の値から...
-
Excel VBA配列をFunctionに渡す
-
3次元配列の記述
-
配列に同じ値を入れる方法
-
2次元動的配列の第一引数のみを...
-
VBAで多次元配列のインデックス...
-
Dim は何の略ですか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
配列数式の解除
-
2つ以上の変数を比較して最大数...
-
配列変数の添字が範囲外ですと...
-
特定のセル範囲で4文字以上入力...
-
VBA 1次元配列を2次元に追加する
-
ListViewで、非表示列って作れ...
-
subの配列引数をoptionalで使う...
-
for each の現在の配列ポインタ...
-
VB6 配列を初期化したい
-
エクセルで最小値から0を除く方法
-
2次元動的配列の第一引数のみを...
-
VBのFunctionで、配列を引数...
-
配列を任意の数値で埋める方法
-
Dim は何の略ですか?
-
Excel-VBAの配列「Public Const...
-
配列内の内容を全て表示する方法
-
Excel VBA配列をFunctionに渡す
-
[VB.net] StringからByte配列へ...
-
《エクセル2000》A列・B列の商...
-
ヤマ括弧でくくられたテキスト...
おすすめ情報